GATE CS 2020 Q5 — Binary Search Trees

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

Given the preorder traversal:
Preorder: $15, 10, 12, 11, 20, 18, 16, 19$

Sorting these elements gives the inorder traversal:
Inorder: $10, 11, 12, 15, 16, 18, 19, 20$

Step 1: Reconstructing the BST

• The first element in the preorder traversal is the root: $15$.
• Elements smaller than $15$ ($\{10, 11, 12\}$) form the left subtree.
• Elements larger than $15$ ($\{16, 18, 19, 20\}$) form the right subtree.

By recursively applying this logic, we construct the unique BST:

       15
      /  \
    10    20
     \    /
     12  18
     /  /  \
    11 16  19

Step 2: Finding the Postorder Traversal

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

• Postorder of Left Subtree (rooted at $10$):
  • Left of $10$: $\emptyset$
  • Right of $10$ (rooted at $12$): Left child is $11$, so postorder is $11, 12$.
  • Root: $10$
  • Result: $11, 12, 10$
• Postorder of Right Subtree (rooted at $20$):
  • Left of $20$ (rooted at $18$): Left child is $16$, right child is $19$, so postorder is $16, 19, 18$.
  • Right of $20$: $\emptyset$
  • Root: $20$
  • Result: $16, 19, 18, 20$
• Combine with Root ($15$):
  $\text{Postorder} = [11, 12, 10] + [16, 19, 18, 20] + [15] = 11, 12, 10, 16, 19, 18, 20, 15$

This matches Option B.