325 views
Given the preorder/postorder and inorder traversal of a binary tree, we can always construct a unique binary tree (I think so, correct me if I am wrong)

Construct a binary tree with the nodes A, B, C such that its preorder traversal is ABC and its inorder traversal is CAB.
asked in DS | 325 views
0

Construct a binary tree with the nodes A, B, C such that its preorder traversal is ABC and its inorder traversal is CAB

such tree can't be constructed.

0
So it means that given preorder/postorder and inorder, there is no guarantee that one can come up with a tree. But if one does come up with a tree, then it is guaranteed be unique, am I right?

unique tree can be generated

(preorder and inorder)=    yes

(postorder and inorder)=  yes

( preorder and postorder )=  no

(inorder= cab and preorder=abc) => such tree dosnt exist.
0
So it means that given preorder/postorder and inorder, there is no guarantee that one can come up with a tree. But if one does come up with a tree, then it is guaranteed be unique, am I right?
0
no, if inorder is given with any other traversal then tree will be constructed as well as unique.....
0
then why not in this case? here also inorder is given as well as a preorder ! But we cant find an unique tree !!
0
i this ques preorder and inorder given are not correct for any tree. and if they are correctly given we can create a unique tree.
+1

1
2