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

~150s

From BST preorder to postorder

The preorder traversal of a binary search tree is 50, 30, 20, 40, 70, 60, 80. What is its postorder traversal?

Show the answer and the worked solution

Correct answer: D.

20, 40, 30, 60, 80, 70, 50

Worked solution

  1. The first preorder key is the root, so 50 is the root.
  2. Keys smaller than 50 form the left subtree — 30, 20, 40 — and the larger ones form the right subtree — 70, 60, 80.
  3. The left subtree has root 30 with 20 on its left and 40 on its right, so its postorder is 20, 40, 30.
  4. The right subtree has root 70 with 60 on its left and 80 on its right, so its postorder is 60, 80, 70.
  5. Postorder visits left, right, root, giving 20, 40, 30, 60, 80, 70, 50.

Answer: 20, 40, 30, 60, 80, 70, 50.

The idea

A BST needs only one traversal to be reconstructed, because sorting the keys supplies the inorder traversal for free. Recurse on the value split rather than drawing the whole tree.

Shortcut. Postorder puts each subtree's root after its children: 30 must follow 20 and 40, and 70 must come just before the final 50, and only one option has both.

Common trap. "20, 30, 40, 50, 60, 70, 80" is the sorted order, which is the inorder traversal of any BST, not the postorder.

Data Structures & Algorithms

18 of 40

Level

Hard

Target time

~150s

From BST preorder to postorder — Aptitude Question

From BST preorder to postorder: The preorder traversal of a binary search tree is 50, 30, 20, 40, 70, 60, 80. Answer and worked solution on CodeKairo.

Question

The preorder traversal of a binary search tree is 50, 30, 20, 40, 70, 60, 80. What is its postorder traversal?

Options

  1. 20, 30, 40, 50, 60, 70, 80
  2. 20, 30, 40, 60, 80, 70, 50
  3. 20, 40, 60, 80, 30, 70, 50
  4. 20, 40, 30, 60, 80, 70, 50
Show the answer and the worked solution

Correct answer: D. 20, 40, 30, 60, 80, 70, 50

Worked solution

  1. The first preorder key is the root, so 50 is the root.
  2. Keys smaller than 50 form the left subtree — 30, 20, 40 — and the larger ones form the right subtree — 70, 60, 80.
  3. The left subtree has root 30 with 20 on its left and 40 on its right, so its postorder is 20, 40, 30.
  4. The right subtree has root 70 with 60 on its left and 80 on its right, so its postorder is 60, 80, 70.
  5. Postorder visits left, right, root, giving 20, 40, 30, 60, 80, 70, 50.

Answer: 20, 40, 30, 60, 80, 70, 50.

The idea

A BST needs only one traversal to be reconstructed, because sorting the keys supplies the inorder traversal for free. Recurse on the value split rather than drawing the whole tree.

Shortcut. Postorder puts each subtree's root after its children: 30 must follow 20 and 40, and 70 must come just before the final 50, and only one option has both.

Common trap. "20, 30, 40, 50, 60, 70, 80" is the sorted order, which is the inorder traversal of any BST, not the postorder.

All Data Structures & Algorithms questions · placement mock tests