Computer Sciences > GATE 2025 SET-1 > Trees
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(log2n) time in the worst case.
D
Every BST is also a Min-Heap.

Correct : a and b

Statement A: The maximum length of a path from the root node to any other node is (n-1).
Analysis: In a skewed BST (all nodes in a single line), the path from root to the deepest node has (n-1) edges.
Example: BST with nodes 1→2→3→4→5 has maximum path length = 4 = (5-1)
Result: TRUE ✓

Statement B: An inorder traversal will always produce a sorted sequence of elements.
Analysis: By definition of BST, left subtree < root < right subtree. Inorder traversal (Left→Root→Right) always visits nodes in ascending order.
Example: BST with root 5, left child 3, right child 7 gives inorder: 3, 5, 7 (sorted)
Result: TRUE ✓

Statement C: Finding an element takes O(log₂n) time in the worst case.
Analysis: In the worst case, BST becomes skewed (like a linked list) and finding an element takes O(n) time, not O(log₂n).
O(log₂n) is only for balanced BST, not for any BST.
Result: FALSE ✗

Statement D: Every BST is also a Min-Heap.
Analysis: Min-Heap property: parent < both children (for all nodes).
BST property: left child < parent < right child.
In BST, the right child can be greater than parent, violating Min-Heap property.
Example: BST with root 5, left child 3, right child 7. Here 7 > 5, so not a Min-Heap.
Result: FALSE ✗

Answer: A and B are TRUE

Similar Questions

Consider a complete binary tree with 7 nodes. Let A denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root....
#1081 Fill in the Blanks
Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the leaves, t...
#1271 Fill in the Blanks
Consider a binary tree T in which every node has either zero or two children. Let n>0 be the number of nodes in T.Which ONE of the following is the number of no...
#1421 MCQ

Related Topics

No tags found

Unique Visitor Count

Total Unique Visitors

Loading......