GATE CS 2011 Q29 — Trees

To form a Binary Search Tree (BST) from a given set of $n$ distinct elements, the elements must satisfy the BST property. Specifically, the in-order traversal of any BST must produce the elements in a strictly sorted (ascending) order.

For any fixed, unlabeled binary tree structure with $n$ nodes:

1. The in-order traversal visits the $n$ nodes in a unique, fixed sequence of positions.
2. Since the $n$ elements are distinct, there is exactly one unique sorted arrangement of these elements.

To satisfy the BST property, we must assign the $i$-th smallest element of our sorted set to the $i$-th node visited during the in-order traversal of the tree, for all $1 \le i \le n$.

Since both the sorted sequence of elements and the in-order traversal path of the tree structure are unique, there is exactly $1$ way to populate the given tree structure to make it a BST.

Therefore, the correct option is B.