GATE CS 2017 Set 2 Q36 — Binary Search Trees

For any Binary Search Tree (BST), the in-order traversal is always sorted in ascending order. Sorting the given pre-order elements gives the in-order traversal:

$$\text{In-order: } 2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20$$

Using the given pre-order traversal ($12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20$), we can reconstruct the tree recursively:

• The first element of the pre-order traversal, $12$, is the root.
• Elements smaller than $12$ form the left subtree: $\{2, 6, 7, 8, 9, 10\}$. Its pre-order is $8, 6, 2, 7, 9, 10$, making $8$ the root. Following this recursively, the post-order for the left subtree is: $$2, 7, 6, 10, 9, 8$$
• Elements larger than $12$ form the right subtree: $\{15, 16, 17, 19, 20\}$. Its pre-order is $16, 15, 19, 17, 20$, making $16$ the root. Following this recursively, the post-order for the right subtree is: $$15, 17, 20, 19, 16$$

Combining these with the root ($12$) at the end (since post-order is $\text{Left} \to \text{Right} \to \text{Root}$), we get:

$$\text{Post-order: } 2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12$$

This matches Option B.