AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Hardtreetraversal

~150s

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. What is its postorder traversal?

Show the answer and the worked solution

Correct answer: A.

D E B F C A

Worked solution

  1. Preorder begins with the root, so A is the root.
  2. In the inorder list, D B E lies left of A and C F lies right of it.
  3. 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.
  4. The preorder of the right subtree is C F, and inorder C F puts F to the right of C.
  5. Postorder visits left, then right, then root: D E B for the left subtree, F C for the right, then A, giving D 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.

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.

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

  1. D E B F C A
  2. D B E F C A
  3. D E B C F A
  4. E D B F C A
Show the answer and the worked solution

Correct answer: A. D E B F C A

Worked solution

  1. Preorder begins with the root, so A is the root.
  2. In the inorder list, D B E lies left of A and C F lies right of it.
  3. 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.
  4. The preorder of the right subtree is C F, and inorder C F puts F to the right of C.
  5. Postorder visits left, then right, then root: D E B for the left subtree, F C for the right, then A, giving D 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