The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16,…
2020
The 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 ?
- A.
10, 11, 12, 15, 16, 18, 19, 20
- B.
11, 12, 10, 16, 19, 18, 20, 15
- C.
20, 19, 18, 16, 15, 12, 11, 10
- D.
19, 16, 18, 20, 11, 12, 10, 15
Attempted by 276 students.
Show answer & explanation
Correct answer: B
Key insight: build the BST from the preorder and then do a postorder (left, right, root).
Root is 15 (first in preorder).
Left subtree (values < 15) from preorder: 10, 12, 11. Its postorder is 11, 12, 10.
Right subtree (values > 15) from preorder: 20, 18, 16, 19. Its postorder is 16, 19, 18, 20.
Combine left-subtree postorder, right-subtree postorder, then the root to get the full postorder: 11, 12, 10, 16, 19, 18, 20, 15