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.

The Gateway to Computer Science Excellence

0 votes

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.

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

+2 votes

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.

(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 !!

52,217 questions

59,907 answers

201,098 comments

118,144 users