Project ForgeThe preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following is the postorder traversal of the tree?
- A10, 11, 12, 15, 16, 18, 19, 20
- 11, 12, 10, 16, 19, 18, 20, 15
- C20, 19, 18, 16, 15, 12, 11, 10
- D19, 16, 18, 20, 11, 12, 10, 15
Explanation
Reconstruct via the BST property: root=15. Left subtree (values<15): 10,12,11 — root 10, whose right child is 12 (since 12>10), which has a left child 11 (since 11<12). Right subtree (values>15): 20,18,16,19 — root 20, whose left child is 18 (since all of 18,16,19<20 go left), 18 has left child 16 and right child 19. Postorder (left,right,root) of the 10-subtree: 11,12,10. Postorder of the 20-subtree: 16,19,18,20. Full postorder = [11,12,10] + [16,19,18,20] + 15 = 11,12,10,16,19,18,20,15 — matching option B exactly.
Source: GATE CS 2020 (2020)
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.