Question 43

The preorder traversal sequence is:

In a Binary Search Tree (BST), the inorder traversal is strictly ascending:

We can reconstruct the BST:

1. The first element of preorder is the root: 30.
2. Elements less than 30 form the left subtree: preorder $[20, 10, 15, 25, 23]$.
   • Root of left subtree is 20.
   • Left of 20: $[10, 15]$. Root is 10, with right child 15.
   • Right of 20: $[25, 23]$. Root is 25, with left child 23.
3. Elements greater than 30 form the right subtree: preorder $[39, 35, 42]$.
   • Root of right subtree is 39.
   • Left child of 39 is 35.
   • Right child of 39 is 42.

Now compute the postorder traversal (Left, Right, Root):

• Left subtree of 10: empty. Right subtree: 15. Root: 10 $\rightarrow [15, 10]$.
• Left subtree of 25: 23. Right subtree: empty. Root: 25 $\rightarrow [23, 25]$.
• Subtree rooted at 20: Left is $[15, 10]$, Right is $[23, 25]$, Root is 20 $\rightarrow [15, 10, 23, 25, 20]$.
• Subtree rooted at 39: Left is 35, Right is 42, Root is 39 $\rightarrow [35, 42, 39]$.
• Whole tree: Left is $[15, 10, 23, 25, 20]$, Right is $[35, 42, 39]$, Root is 30.

Combining these gives the postorder traversal:

This matches option (D).