Postorder traversal of a given binary search tree T produces following…
2017
Postorder traversal of a given binary search tree T produces following sequence of keys :
3, 5, 7, 9, 4, 17, 16, 20, 18, 15, 14
Which one of the following sequences of keys can be the result of an in-order traversal of the tree T ?
- A.
3, 4, 5, 7, 9, 14, 20, 18, 17, 16, 15
- B.
20, 18, 17, 16, 15, 14, 3, 4, 5, 7, 9
- C.
20, 18, 17, 16, 15, 14, 9, 7, 5, 4, 3
- D.
3, 4, 5, 7, 9, 14, 15, 16, 17, 18, 20
Attempted by 595 students.
Show answer & explanation
Correct answer: D
Answer: 3, 4, 5, 7, 9, 14, 15, 16, 17, 18, 20
Reason: In-order traversal of a binary search tree visits keys in ascending order. So the valid in-order sequence must be the sorted list of all keys present in the tree.
From the postorder sequence, the last key is the tree root: 14. Split the earlier keys into left (<14): 3, 5, 7, 9, 4 and right (>14): 17, 16, 20, 18, 15.
Reconstruct left subtree from 3, 5, 7, 9, 4: last is 4 so its root is 4. Left child is 3. Right subtree postorder 5, 7, 9 has root 9, whose left subtree has root 7 with left child 5.
Reconstruct right subtree from 17, 16, 20, 18, 15: last is 15 so its root is 15. Its right subtree postorder 17, 16, 20, 18 has root 18. For 18, left postorder 17, 16 has root 16 with right child 17, and right child is 20.
Now perform in-order (left, root, right) on the whole tree: left subtree gives 3, 4, 5, 7, 9; root 14; right subtree gives 15, 16, 17, 18, 20. Combining yields 3, 4, 5, 7, 9, 14, 15, 16, 17, 18, 20.