The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+14 votes

Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely?

  1. preorder and postorder

  2. inorder and postorder

  3. preorder and inorder

  4. level order and postorder

  1. I only
  2. II, III
  3. III only
  4. IV only
asked in DS by Veteran (52k points) | 1.8k views

To add

Even if all Postorder, Preorder and Levelorder.are given tree cannot be uniquely determined.

If we know the binary tree is full then we can construct even using preorder and postorder traversal. (not given in this question)

See this

3 Answers

+17 votes
Best answer

Following combination can uniquely identify a tree.

  • Inorder and Preorder.
  • Inorder and Postorder.
  • Inorder and Level-order.

And following do not.

  • Postorder and Preorder.
  • Preorder and Level-order.
  • Postorder and Level-order.

Answer: B

answered by Active (3.4k points)
edited by
even preorder, postorder and level order combinedly not identify uniqely
+12 votes
Option b is correct i just draw a tree wrote the preorder,inorder,postorder,level order traversals I find out the options I and IV cant derive a unique tree.
answered by Boss (14.4k points)
we can have more than 1 no of trees of same preorder and postorder so a tree uniquely can not be find using the preorder and post order traversal.

even if three of them (Pre, Post and Level) are given, the tree can not be constructed. Inorder is must.

+3 votes
answered by Boss (10.5k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,541 questions
54,084 answers
70,994 users