GATE CS 2024 Set 2 Q29 — Binary Search Trees

The correct option is A.

A fundamental property of any Binary Search Tree (BST) is that its inorder traversal always visits the nodes in sorted (ascending) order.

Since $V$ is a set of distinct integers, sorting the elements of $V$ in ascending order uniquely determines the inorder traversal of $T$, regardless of the order in which the elements were inserted to construct the tree.

Why other options are incorrect:

The root node, preorder traversal, and postorder traversal depend entirely on the shape of the tree, which in turn depends on the insertion sequence of the elements. Since the insertion sequence is unknown, these cannot be uniquely determined.

Example:

Let $V = \{1, 2, 3\}$.

• Case 1: If the insertion sequence is $2, 1, 3$:
  • The root is $2$.
  • Preorder traversal: $2, 1, 3$
  • Postorder traversal: $1, 3, 2$
  • Inorder traversal: $1, 2, 3$
• Case 2: If the insertion sequence is $1, 2, 3$:
  • The root is $1$.
  • Preorder traversal: $1, 2, 3$
  • Postorder traversal: $3, 2, 1$
  • Inorder traversal: $1, 2, 3$

As shown, while the root, preorder, and postorder traversals change based on the insertion sequence, the inorder traversal remains uniquely $1, 2, 3$ in all cases.