GATE CS 2015 Set 1 Q.20 (CS Q.10): Binary Trees, Binary Search Trees and Balanced Trees

Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)?

I. $3, 5, 7, 8, 15, 19, 25$
II. $5, 8, 9, 12, 10, 15, 25$
III. $2, 7, 10, 8, 14, 16, 20$
IV. $4, 6, 7, 9, 18, 20, 25$

I and IV only

II and III only

II and IV only

II only

Official answer and solution

Official answer: A
From: Official GATE 2015 answer key

Solution

Recall that the inorder traversal of any Binary Search Tree produces a monotonically non-decreasing (strictly increasing for distinct keys) sequence.

In a Binary Search Tree (BST), the left subtree contains keys smaller than the root, and the right subtree contains keys greater than the root.
An inorder traversal visits $\\text{Left} \\to \\text{Root} \\to \\text{Right}$ , which always outputs keys in strictly ascending sorted order.

Testing each sequence:

I: $3 < 5 < 7 < 8 < 15 < 19 < 25$ (Strictly increasing: Valid)
II: $5, 8, 9, 12, 10, 15, 25$ (Contains $12 > 10$ , not sorted: Invalid)
III: $2, 7, 10, 8, 14, 16, 20$ (Contains $10 > 8$ , not sorted: Invalid)
IV: $4 < 6 < 7 < 9 < 18 < 20 < 25$ (Strictly increasing: Valid)

Therefore, only I and IV are correct inorder traversal sequences of binary search trees (option A).

Final answer

Common trap

Confusing inorder traversal with preorder or postorder traversal, where keys do not appear in sorted order.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 1
Question: 20 of 65, printed as CS Q.10
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source