GATE CS 2015 Set 1 Q10 — Binary Search Trees

A fundamental property of a Binary Search Tree (BST) is that its inorder traversal always yields the keys in a strictly increasing (sorted) order.

Let us analyze the given sequences:

• I. $3, 5, 7, 8, 15, 19, 25$: This sequence is sorted in strictly increasing order. Therefore, it is a valid inorder traversal of a BST.
• II. $5, 8, 9, 12, 10, 15, 25$: This sequence is not sorted because $12 > 10$. Therefore, it cannot be an inorder traversal of a BST.
• III. $2, 7, 10, 8, 14, 16, 20$: This sequence is not sorted because $10 > 8$. Therefore, it cannot be an inorder traversal of a BST.
• IV. $4, 6, 7, 9, 18, 20, 25$: This sequence is sorted in strictly increasing order. Therefore, it is a valid inorder traversal of a BST.

Thus, only sequences I and IV are correct inorder traversal sequences of a BST.