GATE CS 2025 Set 1 | Question 26

MSQ · 1 mark

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

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

Answer

(A), (B)

Explanation

  • (A) True: a path from the root visits distinct nodes, so it has at most \(n - 1\) edges, and a skewed BST (keys inserted in sorted order) reaches exactly \(n - 1\).
  • (B) True: every left subtree holds smaller keys and every right subtree larger ones, so left–root–right order lists the keys in increasing order.
  • (C) False: a skewed BST has height \(n - 1\), so a search can take \(O(n)\) time; \(O(\log_{2} n)\) is guaranteed only for balanced trees.
  • (D) False: in a min-heap a parent is smaller than its children, but in a BST any left child is smaller than its parent.

Answer: A, B