The GATE Grind

GATE 2025 CS (CS1) – Question 26

Programming and Data Structures · Trees and Binary Search Trees · 1 mark · Multiple select

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

  1. The maximum length of a path from the root node to any other node is $(n-1)$.
  2. An inorder traversal will always produce a sorted sequence of elements.
  3. Finding an element takes $O(\log_2 n)$ time in the worst case.
  4. Every BST is also a Min-Heap.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) An inorder traversal will always produce a sorted sequence of elements.

Explanation

Inorder traversal of a BST is always sorted. The maximum path length equals n-1 only for a skewed tree, and a skewed BST makes search O(n). A BST need not satisfy the heap property.