GATE CS 2005 Q33 — Binary Search Trees

A fundamental property of any Binary Search Tree (BST) is that its in-order traversal always yields the keys in strictly ascending (sorted) order.

Let's examine the given options to see which sequence is sorted in ascending order:

• Option A: $9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95$ — This sequence is sorted in ascending order.
• Option B: $9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29$ — Not sorted (e.g., $23$ appears after $95$).
• Option C: $29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95$ — Not sorted.
• Option D: $95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29$ — Not sorted in ascending order.

Thus, only the sequence in Option A can represent the in-order traversal of the BST $T$.