GATE CS 2013 Q43 — Binary Search Trees

For any Binary Search Tree (BST), the inorder traversal is always the sorted sequence of its keys in ascending order.

Given the preorder traversal:
Preorder: $30, 20, 10, 15, 25, 23, 39, 35, 42$

Sorting these keys gives the inorder traversal:
Inorder: $10, 15, 20, 23, 25, 30, 35, 39, 42$

Step 1: Reconstructing the BST

1. The first element in the preorder sequence is the root: $30$.
2. Elements smaller than $30$ ($10, 15, 20, 23, 25$) form the left subtree. Elements larger than $30$ ($35, 39, 42$) form the right subtree.
3. For the left subtree, the next element in the preorder sequence is $20$, which becomes the root of this subtree.
   • Keys smaller than $20$ ($10, 15$) go to its left.
   • Keys larger than $20$ ($23, 25$) go to its right.
4. Continuing this process recursively, we construct the unique BST:

       30
      /  \
    20    39
   /  \   / \
  10  25 35 42
   \  /
   15 23

Step 2: Finding the Postorder Traversal

Postorder traversal visits nodes in the order: Left $\rightarrow$ Right $\rightarrow$ Root.

• Left Subtree of $30$:
  • Postorder of left child $20$:
    • Left child of $20$ (rooted at $10$): $15, 10$
    • Right child of $20$ (rooted at $25$): $23, 25$
    • Root: $20$
    This gives: $15, 10, 23, 25, 20$
• Right Subtree of $30$:
  • Postorder of right child $39$:
    • Left child: $35$
    • Right child: $42$
    • Root: $39$
    This gives: $35, 42, 39$
• Root Node: $30$

Combining these, the complete postorder traversal is:
$15, 10, 23, 25, 20, 35, 42, 39, 30$

This matches Option D.