470 views
0 votes
0 votes
If a tree is having only two nodes ( May be A and B). and its preorder and postorder is given, then is it possible to construct unique tree?

2 Answers

Best answer
8 votes
8 votes

No it will not be possible, Its not possible when the number of nodes is greater than 1. You have to have inorder to construct the unique Binary tree.

Let consider the following tree,

Pre-Order (Root-Left-Right) will be : 1, 2

Post-Order (Left-Right-Root) will be : 2, 1

Now consider this tree,

Pre-Order (Root-Left-Right) will be : 1, 2

Post-Order (Left-Right-Root) will be : 2, 1

See, Both are giving the same preorder and postorder traversal. Hence its not possible to have unique Binary tree. 

selected by
0 votes
0 votes
yes possible to construct.

with two nodes A and B if preorder given=AB and postorder will be BA

                                   if preorder is BA then post order will be AB

                        for a tree preorder,postorder cannot be same for a specific structure

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
0 answers
2
damz1499 asked Dec 29, 2022
380 views
1 votes
1 votes
1 answer
4
casberg asked Nov 23, 2021
497 views
What is the smallest and largest number of entries for 2_3 BTree (B2_3 Tree) of height 8 (i.e 8 levels) ? 255 & 6560127 & 21866561 & 255255 & 2186