GATE CS 1997 Q4.5 — Binary Search Trees

For any node $X$ in a Binary Search Tree (BST), the pre-order traversal follows the Root $\rightarrow$ Left $\rightarrow$ Right strategy. This imposes a strict partitioning rule on the pre-order sequence:

• The first element is the root $X$.
• All elements in the sequence following $X$ that are smaller than $X$ (representing the left subtree) must appear before any elements that are larger than $X$ (representing the right subtree).
• This property must hold recursively for every subtree.

Let's analyze the options with the keys $\{1, 2, 3, 4, 5, 6, 7, 8\}$:

1. $5 \ 3 \ 1 \ 2 \ 4 \ 7 \ 8 \ 6$
   • For root $5$, the left subtree is $\{3, 1, 2, 4\}$ and the right subtree is $\{7, 8, 6\}$.
   • For the right subtree root $7$, the elements are $7 \ [8 \ 6]$. Here, $6$ (smaller than $7$) appears after $8$ (larger than $7$). This violates the BST property. Thus, this sequence is invalid.
2. $5 \ 3 \ 1 \ 2 \ 6 \ 4 \ 8 \ 7$
   • For root $5$, the element $4$ (smaller than $5$) appears after $6$ (larger than $5$). This violates the partition property for root $5$. Thus, this sequence is invalid.
3. $5 \ 3 \ 2 \ 4 \ 1 \ 6 \ 7 \ 8$
   • For root $5$, the left subtree sequence is $3 \ 2 \ 4 \ 1$.
   • For subtree root $3$, the element $1$ (smaller than $3$) appears after $4$ (larger than $3$). This violates the partition property for root $3$. Thus, this sequence is invalid.
4. $5 \ 3 \ 1 \ 2 \ 4 \ 7 \ 6 \ 8$
   • For root $5$, the left subtree is $\{3, 1, 2, 4\}$ and the right subtree is $\{7, 6, 8\}$.
   • For subtree root $3$, the left subtree is $\{1, 2\}$ and the right subtree is $\{4\}$. This is valid. For root $1$, the right child is $2$. This is valid.
   • For subtree root $7$, the left subtree is $\{6\}$ and the right subtree is $\{8\}$. This is valid.
   • Since all recursive partitions are valid, this sequence is valid.