GATE CSE 2025 | Set 1 | Question: 16

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\left(\log _{2} n\right)$ time in the worst case.
• D. Every BST is also a Min-Heap.

Comments

The length of a path from the root node to any other node is maximum (n-1) // This statement is 100% true
The maximum length of a path from the root node to any other node is (n-1) // This statement is false (Option A)

Think once!!! Maybe i am wrong but i am confused.

@Arjun 1

---

You have just made two equal statements. Don't overthink it mate. The maximum length of a path from the root node to any other node is n-1 means the length of a path from the root node to any other node cannot exceed n - 1, which is true.

---

Answer A and B,,,https://correctbrain.com/buy/

Answer 1

(A) & (B)

(A) If we have skew tree then maximum length of a path from root node to last node is (n-1)
(B) Yes, in BST, inorder traversal is in sorted sequence
(C) FALSE, exactly opposite to option A. In worst case, we can have O(n)
(D) FALSE, BST has property of left child lesser than root and right child  greater than root, whereas Min-heap has property of both child should be Greater than root.

Answer 2

$\text{Option A) and B) are Correct .}$

A) This statement is True. the maximum length of a path can be $n−1$ in a fully skewed BST.

B) This statement is also True. An inorder traversal visits the left subtree, then the current node, and finally the right subtree, which naturally processes the nodes in ascending order, resulting in a sorted list.

C) This statement is False. The worst-case time complexity for finding an element in a BST is $O(n)$, not  $O\left(\log _{2} n\right)$. This worst-case scenario occurs in fully skewed tree, where the search path may need to traverse every single node, similar to a linear search. The $O\left(\log _{2} n\right)$ time complexity is the best-case and average-case time complexity, which occurs in a balanced tree.

D) This statement is False. 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. While a BST also has an ordering property, it's different. In a BST, the value of the left child is less than the parent, but the value of the right child is greater. This is a different ordering rule than a Min-Heap. For example, the root of a BST is not necessarily the smallest element, but the root of a Min-Heap must be.

Answer 3

(A) In the worst case, a BST can be completely skewed (e.g., when elements are inserted in sorted order), forming a linear chain of $n$ nodes. The path from the root to the deepest leaf then contains $n - 1$ edges, which is the maximum possible for any binary tree with $n$ nodes. Hence, this statement is true.

(B) By the defining property of a BST, all keys in the left subtree of a node are less than the node’s key, and all keys in the right subtree are greater. An inorder traversal (left → root → right) recursively visits keys in increasing order, and thus always yields a sorted sequence. This holds for every BST, so the statement is true.

(C) The worst-case time complexity for searching in a BST is $O(n)$, which occurs when the tree is degenerate (height $n - 1$). The bound $O(\log n)$ applies only to balanced BSTs, not to arbitrary BSTs. Therefore, this statement is false.

(D) A Min-Heap requires that each node’s key be less than or equal to its children’s keys. A BST imposes an ordering between left/right subtrees but does not enforce a parent-child magnitude constraint compatible with the heap property. For example, the BST with root $2$, left child $1$, and right child $3$ violates the Min-Heap condition (since $1 < 2$). Thus, this statement is false.

Final Answer: (A), (B)

Comments

Nice explaination 👍

Answer 4

a,b are true.

c is false, as finding element in BST in worst case takes O(n).

d is false, In BST values of left subtree of node x≤ x ≤ values of right subtree of node 'x'. 

Whereas in Min heap, parent key value is ≤ child node key values.

Answer 5

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

 

Also the question ask for which of the statements are true for ""any"'" BST having n nodes.
​The word "any" in the question implies that the statement must hold true for every valid Binary Search Tree (BST) containing n distinct integers.

 

Option A should be false..

 

The correct answer should be only option B

Answer 6

option A is true ,the maximum length of the binary search tree with 'n' nodes is n-1,ans the minimum length of it with the n nodes is logn

option B is true, yes in-order traversal of BST is alwasy sorted

optiion C is false,BST is some times form  skewed structure (or) entering nodes which are greater than the parent node ,at that time there is a possibility of getting o(n) for searching an element in worst case

option D id false , every binary search tree[parent>elements in leftsubtree and parent<elements in rightsubtree] cant be a min heap [parent<=child]