1.8k 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 | 1.8k views
+4

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)

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.

edited
0
even preorder, postorder and level order combinedly not identify uniqely
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.
+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.
+11

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

1
2
3
4
5
6