Question

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

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

Hint:

In a binary search tree, an inorder traversal always results in sorted elements. Additionally, in the worst case of a skewed tree, the maximum height can be \(n - 1\), leading to a linear time complexity for finding elements.

Answer 1

The Correct Option is A, B

Let’s analyze each statement:

(A) The maximum length of a path from the root node to any other node is \( (n - 1) \):
This statement is correct in the worst-case scenario, where the tree is skewed (like a linked list). In such a case, the maximum path length from the root node to any other node will be \( n - 1 \), as each node only has one child.

(B) An inorder traversal will always produce a sorted sequence of elements:
This statement is correct. By definition, an inorder traversal of a binary search tree (BST) visits nodes in ascending order, producing a sorted sequence of elements.

(C) Finding an element takes \( O(\log_2 n) \) time in the worst case:
This statement is incorrect. In the worst case (for a skewed tree), the time complexity for finding an element can be \( O(n) \), not \( O(\log n) \).

(D) Every BST is also a Min-Heap:
This statement is incorrect. A Min-Heap is a complete binary tree where the value of each node is less than or equal to the values of its children. A binary search tree (BST) does not necessarily satisfy the Min-Heap property.

Thus, the correct answers are \( \boxed{A} \) & \( \boxed{B} \).