GATE CS 2025 Set 1 Q16 — Binary Search Trees

Let us analyze each statement for a Binary Search Tree (BST) containing $n$ distinct integers:

• Statement A: True
  In a skewed BST (where each node has at most one child), the nodes are arranged in a linear chain. The path from the root to the deepest node contains all $n$ nodes, which corresponds to exactly $n-1$ edges. Thus, the maximum path length from the root to any other node is $n-1$.
• Statement B: True
  By definition, the binary search tree property states that for any node, all elements in its left subtree are smaller than the node's key, and all elements in its right subtree are greater. An inorder traversal (Left-Root-Right) visits the nodes in strictly increasing order, producing a sorted sequence.
• Statement C: False
  In the worst case (such as a skewed BST), the height of the tree is $O(n)$. Consequently, searching for an element can take $O(n)$ time, not $O(\log_2 n)$.
• Statement D: False
  A Min-Heap requires the key of a parent node to be less than or equal to the keys of its children. A BST requires the left child to be smaller than the parent. For example, in a BST with root $10$ and left child $5$, the parent ($10$) is greater than its child ($5$), which violates the Min-Heap property.

Therefore, the correct options are A and B.