The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25,…
20132013
The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?
- A.
10, 20, 15, 23, 25, 35, 42, 39, 30
- B.
15, 10, 25, 23, 20, 42, 35, 39, 30
- C.
15, 20, 10, 23, 25, 42, 35, 39, 30
- D.
15, 10, 23, 25, 20, 35, 42, 39, 30
Attempted by 231 students.
Show answer & explanation
Correct answer: D
Key insight: reconstruct the BST from the preorder sequence and then perform a postorder traversal (left, right, root).
Build the BST by inserting nodes in preorder: 30 is the root. Left of 30: 20; left of 20: 10 with right child 15; right of 20: 25 with left child 23. Right of 30: 39 with left child 35 and right child 42.
Compute postorder (left, right, root): left subtree → 15, 10, 23, 25, 20. Right subtree → 35, 42, 39.
Final postorder traversal: 15, 10, 23, 25, 20, 35, 42, 39, 30
A video solution is available for this question — log in and enroll to watch it.