GATE 2025 CS1 Q.26: solution and answer

GATE 2025 · CS1Q.26 · 1 mark · MSQ

Which of the following statement(s) is/are TRUE for any binary search tree (BST) having $n$ distinct integers?

(A)
The maximum length of a path from the root node to any other node is $(n - 1)$ .
(B)
An inorder traversal will always produce a sorted sequence of elements.
(C)
Finding an element takes $O (lo g_{2} n)$ time in the worst case.
(D)
Every BST is also a Min-Heap.

See the question in the paper

Answer and solution

ANSWER

The answer is (A) and (B). A root-to-node path in an $n$ -node tree can have at most $n - 1$ edges, and an inorder traversal of any BST gives its keys in sorted order.

Official answer: A, BSource: Official answer key, GATE 2025 CS1 (IIT Roorkee)

Option A (TRUE). A path from the root down to any node is a simple path, so it visits each node at most once. The tree has only $n$ nodes, so such a path has at most $n$ nodes and at most $n - 1$ edges. This limit is actually reached: insert $1, 2, \dots, n$ in increasing order to get a right-skewed BST, and the path from the root $1$ to the node $n$ has exactly $n - 1$ edges. So for every BST on $n$ distinct keys, the longest a root-to-node path can be is $n - 1$ . The statement gives this upper bound. It does not claim that every BST has height $n - 1$ .
Option B (TRUE). At every node, all keys in the left subtree are smaller than the node's key and all keys in the right subtree are larger. An inorder traversal visits the left subtree, then the node, then the right subtree. By induction on the subtree size, each subtree is output in increasing order, then the node's key, which is larger than everything already printed and smaller than everything still to come. So the whole sequence is sorted in increasing order, whatever the shape of the tree.
Option C (FALSE). A search follows one root-to-leaf path, so its worst-case cost is proportional to the height of the tree. In the skewed BST from option A the height is $n - 1$ , and searching for $n$ (or for any key greater than $n$ ) takes $n$ comparisons. That is $Θ (n)$ , not $O (lo g_{2} n)$ . The $O (lo g_{2} n)$ bound holds only for a balanced BST, such as an AVL or red-black tree.
Option D (FALSE). A min-heap needs every parent $\leq$ its children. In a BST, a left child is always smaller than its parent. Take the BST with root $2$ , left child $1$ and right child $3$ : the parent $2$ is greater than its child $1$ , so the min-heap property fails. Any BST where some node has a left child breaks the min-heap property in the same way.
The statements that hold for every BST on $n$ distinct integers are (A) and (B).

KEY IDEA

A root-to-node path cannot repeat a node, so in any $n$ -node tree it has at most $n - 1$ edges. A skewed BST reaches that limit. Inorder traversal of a BST (left, node, right) always gives the keys in sorted order. Search cost depends on the height, which can be as large as $n - 1$ , so an unbalanced BST has $Θ (n)$ worst-case search. A left child is always smaller than its parent, so a BST with any left child cannot be a min-heap.

WATCH OUT FOR

The common mistake is to read (A) as "every BST has height $n - 1$ " and reject it because a balanced BST is only $O (lo g n)$ deep. The statement gives the largest length a root-to-node path can have in any BST, and $n - 1$ is that upper bound. It is reached by a skewed tree. A second mistake is to accept (C) by assuming the BST is balanced. A plain BST has no such guarantee.

From the GATE 2025 CS1 paper. Every question of this paper · Download the full paper · All 26 Trees & heaps questions, with notes

GATE 2025 CS1 Q.26: solution and answer

Answer and solution

More Trees & heaps questions