Question 15

In a BST, an inorder traversal gives the keys in sorted order. Sorting the given keys yields:

Given preorder: 15, 10, 12, 11, 20, 18, 16, 19.

• Root is 15.
• Elements less than 15 belong to the left subtree: preorder [10, 12, 11].
  • Root of left subtree is 10. Left child of 10 is empty (no elements < 10).
  • Right child of 10 is 12 (since 12 > 10). Left child of 12 is 11 (since 11 < 12).
• Elements greater than 15 belong to the right subtree: preorder [20, 18, 16, 19].
  • Root of right subtree is 20. Left child of 20 is 18 (since elements < 20).
  • For node 18, left child is 16 and right child is 19.

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

• Left subtree of 15:
  • Postorder of node 12: left is 11, right is null, root is 12 $\implies [11, 12]$.
  • Postorder of node 10: left is null, right is subtree 12, root is 10 $\implies [11, 12, 10]$.
• Right subtree of 15:
  • Postorder of node 18: left is 16, right is 19, root is 18 $\implies [16, 19, 18]$.
  • Postorder of node 20: left is subtree 18, right is null, root is 20 $\implies [16, 19, 18, 20]$.
• Append the root 15:
  $$\text{Full Postorder: } 11, 12, 10, 16, 19, 18, 20, 15$$