The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
1.6k views

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 (59.7k points) | 1.6k views
+3

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 https://www.geeksforgeeks.org/full-and-complete-binary-tree-from-given-preorder-and-postorder-traversals/

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 (4.2k points)
edited by
0
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)
+1
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.
+10

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

http://www.cmi.ac.in/~madhavan/courses/programming06/lecture12-21sep2006.txt

+3 votes
Answer:

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

44,199 questions
49,669 answers
163,546 comments
65,818 users