GATE2025_CS1_Q26

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

Note: This is a Multiple Select Question (MSQ). One or more options may be correct.

✅ Final Answer:

The correct options are (A) and (B).

🔹 Short Answer:

(A) is true because a skewed BST with n nodes has a maximum path length of n-1. (B) is true as it's the fundamental property of a BST that an inorder traversal yields sorted data. (C) is false because the worst-case search time in a skewed BST is O(n). (D) is false because the ordering rules for a BST (left < root < right) and a Min-Heap (root < children) are mutually exclusive.

🔸 Long Answer:

This question tests the fundamental properties of Binary Search Trees (BSTs), particularly in their worst-case scenarios, and compares them against other data structures like Min-Heaps.

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

This statement is TRUE. The question asks for the maximum possible path length in any BST. This maximum is achieved in a degenerate or skewed tree. For example, if we insert the integers 1, 2, 3, 4, 5 in that order, each new node becomes the right child of the previous one. The resulting tree is essentially a linked list. The path from the root (1) to the deepest node (5) consists of 4 edges (5-1 = 4). For n nodes, this path length is n-1.

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

This statement is TRUE. This is the defining characteristic and primary advantage of a BST. The BST property states that for any given node, all values in its left subtree are smaller, and all values in its right subtree are larger. The inorder traversal algorithm (visit left subtree, visit root, visit right subtree) recursively applies this logic, guaranteeing that the nodes are visited in ascending order of their values. [2]

(C) Finding an element takes O(log₂ n) time in the worst case.

This statement is FALSE. The O(log n) search time is characteristic of a balanced BST. The question specifies "any" BST. In the worst-case scenario of a skewed tree (as shown for option A), the search operation degrades to a linear scan of all n nodes. Therefore, the worst-case time complexity for finding an element in a general BST is O(n). [4]

(D) Every BST is also a Min-Heap.

This statement is FALSE. A BST and a Min-Heap have conflicting ordering properties.

• BST Property: For any node `P`, `value(left_child) < value(P) < value(right_child)`.
• Min-Heap Property: For any node `P`, `value(P) < value(left_child)` and `value(P) < value(right_child)`. [1, 3]

These two rules are mutually exclusive. For example, in a BST, the root is not guaranteed to be the smallest element, whereas in a Min-Heap, it must be. [1] Thus, a BST cannot be a Min-Heap (unless it contains only one node).

Bibliography:
[1] Quora. (2022). What is the difference between binary search tree and min heap?. Retrieved from Quora.
[2] Stack Overflow. (2011). Heap vs Binary Search Tree (BST). Retrieved from Stack Overflow.
[3] Quora. (2017). What is the difference between binary search tree and min heap?. Retrieved from Quora.
[4] GeeksforGeeks. (2024). Difference between Binary Search Tree and Binary Heap. Retrieved from GeeksforGeeks.
[5] GeeksforGeeks. (2022). Comparison between Heap and Tree. Retrieved from GeeksforGeeks.

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.