Rebuilding a tree from two traversals — Aptitude Question
Rebuilding a tree from two traversals: A binary tree has preorder A B D E C F and inorder D B E A C F. Answer and worked solution on CodeKairo.
- Topic: Data Structures & Algorithms
- Section: Programming MCQs
- Difficulty: Hard
- Time target: 150 seconds
Question
A binary tree has preorder A B D E C F and inorder D B E A C F. What is its postorder traversal?
Options
- D E B F C A
- D B E F C A
- D E B C F A
- E D B F C A
Show the answer and the worked solution
Correct answer: A. D E B F C A
Worked solution
- Preorder begins with the root, so A is the root.
- In the inorder list,
D B Elies left of A andC Flies right of it. - The preorder of the left subtree is
B D E, so B is its root with D on the left and E on the right. - The preorder of the right subtree is
C F, and inorderC Fputs F to the right of C. - Postorder visits left, then right, then root:
D E Bfor the left subtree,F Cfor the right, thenA, givingD E B F C A.
Answer: D E B F C A.
The idea
Preorder or postorder names the root; inorder splits the rest into the two subtrees. Either pair reconstructs the tree, but preorder with postorder does not — those two cannot tell a left child from a right one.
Shortcut. Each subtree ends with its own root: the left subtree rooted at B reads D E B, the right rooted at C with F on its right reads F C, then A.
Common trap. "D B E F C A" copies the left subtree in inorder (D B E) instead of postorder, putting B before its right child E.
All Data Structures & Algorithms questions · placement mock tests