GATE CS 2025 Set 1 Q.26: Binary Trees, Binary Search Trees and Balanced Trees

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

The maximum length of a path from the root node to any other node is $(n - 1)$ .

An inorder traversal will always produce a sorted sequence of elements.

Finding an element takes $O(\log_2 n)$ time in the worst case.

Every BST is also a Min-Heap.

Official answer and solution

Solution

Check each property for an arbitrary (possibly unbalanced/skewed) BST with $n$ distinct keys.

(A) True: In the worst case (a degenerate/skewed BST where every node has at most one child), the path from the root to the deepest leaf has $n - 1$ edges.
(B) True: By the BST ordering property (left subtree $< \text{node} <$ right subtree), an inorder traversal always visits keys in strictly increasing (sorted) order.
(C) False: In a skewed BST, finding an element takes $\Theta(n)$ time in the worst case, not $O(\log_2 n)$ .
(D) False: A BST with a non-empty left child has a left child smaller than its parent, violating the Min-Heap property.

Final answer

Options (A), (B)

Common trap

Assuming a BST is balanced in the worst case and selecting (C).

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

Paper: GATE 2025 Computer Science and Information Technology - Session 1 (CS1)
Question: 26 of 65
Section: Computer Science and Information Technology

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