Question 36

Given pre-order traversal: 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20.
Since this is a BST, the in-order traversal consists of these keys sorted in ascending order:
2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20.

Reconstruct the BST:

1. The root is 12 (first element in pre-order).
2. Keys smaller than 12 form the left subtree: $\{8, 6, 2, 7, 9, 10\}$ with root 8.
   • Left of 8: $\{6, 2, 7\}$ with root 6, left child 2, right child 7.
   • Right of 8: $\{9, 10\}$ with root 9 and right child 10.
3. Keys greater than 12 form the right subtree: $\{16, 15, 19, 17, 20\}$ with root 16.
   • Left of 16: 15.
   • Right of 16: $\{19, 17, 20\}$ with root 19, left child 17, right child 20.

Compute post-order traversal (Left, Right, Root):

• Subtree at 6: left = 2, right = 7, root = 6 $\implies$ 2, 7, 6.
• Subtree at 9: left = none, right = 10, root = 9 $\implies$ 10, 9.
• Subtree at 8: left = 2, 7, 6, right = 10, 9, root = 8 $\implies$ 2, 7, 6, 10, 9, 8.
• Subtree at 19: left = 17, right = 20, root = 19 $\implies$ 17, 20, 19.
• Subtree at 16: left = 15, right = 17, 20, 19, root = 16 $\implies$ 15, 17, 20, 19, 16.
• Root 12: left subtree followed by right subtree followed by root 12:
  2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12.
  This matches option B.