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?
10, 11, 12, 15, 16, 18, 19, 20
11, 12, 10, 16, 19, 18, 20, 15
20, 19, 18, 16, 15, 12, 11, 10
19, 16, 18, 20, 11, 12, 10, 15
ANSWER
The postorder traversal of the tree is 11, 12, 10, 16, 19, 18, 20, 15 — option B.
Official answer: BSource: Official answer key, GATE 2020 CS (IIT Delhi)
Root of the BST is the first preorder element: 15.
Split the remaining preorder elements into those less than 15 (left subtree preorder) and those greater than 15 (right subtree preorder): left = 10, 12, 11; right = 20, 18, 16, 19.
Reconstruct the left subtree from preorder (10, 12, 11): root 10; remaining values 12, 11 are both greater than 10, so they form 10's right subtree, whose preorder is 12, 11 — root 12, with 11 (< 12) as its left child. So: 10 has right child 12, which has left child 11.
Reconstruct the right subtree from preorder (20, 18, 16, 19): root 20; remaining values 18, 16, 19 are all less than 20, so they form 20's left subtree, whose preorder is 18, 16, 19 — root 18, then 16 (< 18) is its left child and 19 (> 18) is its right child. So: 20 has left child 18, which has left child 16 and right child 19.
Postorder visits (left subtree, then right subtree, then root) recursively. For the subtree rooted at 10: postorder(10) = postorder(right child 12) + [10]; postorder(12) = [11] (left child) + [12] = 11, 12. So postorder(10) = 11, 12, 10.
For the subtree rooted at 20: postorder(20) = postorder(left child 18) + [20]; postorder(18) = [16] (left) + [19] (right) + [18] = 16, 19, 18. So postorder(20) = 16, 19, 18, 20.
Combine at the overall root 15: postorder(whole tree) = postorder(left subtree, rooted 10) + postorder(right subtree, rooted 20) + [15] = 11, 12, 10, 16, 19, 18, 20, 15.
This sequence exactly matches option B.
KEY IDEA
A BST's preorder uniquely determines its shape: the root is first, and the remaining elements split into two contiguous runs — those less than the root (left subtree preorder) and those greater (right subtree preorder), recursively. Once the tree is reconstructed, postorder = left subtree postorder, then right subtree postorder, then root, applied recursively.
WATCH OUT FOR
Confusing preorder-to-postorder conversion with just reversing the preorder sequence (which would wrongly suggest something like 19,16,18,20,11,12,10,15, option D) — reversing preorder only produces a valid postorder-like listing for specific tree shapes, not in general; the visit order of left/right children must actually be respected via correct BST reconstruction.
From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 26 Trees & heaps questions, with notes
