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

binary search tree GATE computer science 2025 BST properties binary trees O(log n) time complexity inorder traversal sorted Min Heap definition worst case BST computer science gate binary search tree properties

Unique Visitor Count

Total Unique Visitors

Loading......