Project ForgeThe 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?
- A10, 20, 15, 23, 25, 35, 42, 39, 30
- B15, 10, 25, 23, 20, 42, 35, 39, 30
- C15, 20, 10, 23, 25, 42, 35, 39, 30
- 15, 10, 23, 25, 20, 35, 42, 39, 30
Explanation
Reconstruct the BST from the preorder sequence using the BST ordering property: root=30; everything <30 (20,10,15,25,23) is the left subtree, everything >30 (39,35,42) is the right subtree. Within the left subtree, root=20, with left child 10 (which has a right child 15, since 15>10) and right child 25 (which has a left child 23, since 23<25). Within the right subtree, root=39, with left child 35 and right child 42. Postorder (left, right, root) of the whole tree: from the 10-node: 15,10; from the 25-node: 23,25; combine at 20: 15,10,23,25,20; from the 39-node: 35,42,39; combine at root 30: 15,10,23,25,20,35,42,39,30 — matching option D exactly.
Source: GATE CS 2013 (2013)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.