GATE CS Binary Search Trees Previous Year Questions

GATE CS 2025 Set 1 | Question 26

MSQ · 1 mark

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

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

Explanation

Answer: (A), (B)

(A) True: a path from the root visits distinct nodes, so it has at most \(n - 1\) edges, and a skewed BST (keys inserted in sorted order) reaches exactly \(n - 1\).
(B) True: every left subtree holds smaller keys and every right subtree larger ones, so left–root–right order lists the keys in increasing order.
(C) False: a skewed BST has height \(n - 1\), so a search can take \(O(n)\) time; \(O(\log_{2} n)\) is guaranteed only for balanced trees.
(D) False: in a min-heap a parent is smaller than its children, but in a BST any left child is smaller than its parent.

Answer: A, B

GATE CS 2025 Set 2 | Question 35

NAT · 1 mark

Suppose the values \(10, -4, 15, 30, 20, 5, 60, 19\) are inserted in that order into an initially empty binary search tree. Let \(T\) be the resulting binary search tree. The number of edges in the path from the node containing \(19\) to the root node of \(T\) is ___________. (Answer in integer)

Your answer

Explanation

Answer: 4

Insert the keys in order, going left for a smaller key and right for a larger one:

10 is the root; \(-4\) goes left of 10 and 15 right of 10.
30 goes right of 15, and 20 goes left of 30.
5 goes right of \(-4\), and 60 goes right of 30.
19 is larger than 10 and 15 but smaller than 30 and 20, so it becomes the left child of 20.

The path from 19 up to the root is \(19 \to 20 \to 30 \to 15 \to 10\): 4 edges, i.e. 19 sits at depth 4.

Answer: 4

GATE CS 2024 Set 2 | Question 39

MCQ · 2 marks · −0.66

You are given a set \(V\) of distinct integers. A binary search tree \(T\) is created by inserting all elements of \(V\) one by one, starting with an empty tree. The tree \(T\) follows the convention that, at each node, all values stored in the left subtree of the node are smaller than the value stored at the node. You are not aware of the sequence in which these values were inserted into \(T\), and you do not have access to \(T\).

Which one of the following statements is TRUE?

Inorder traversal of \(T\) can be determined from \(V\) Root node of \(T\) can be determined from \(V\) Preorder traversal of \(T\) can be determined from \(V\) Postorder traversal of \(T\) can be determined from \(V\)

Explanation

Answer: (A)

An inorder traversal visits the left subtree, then the node, then the right subtree. In a binary search tree with smaller values on the left, this always lists the keys in increasing order, whatever the shape of the tree. So sorting \(V\) gives the inorder traversal of \(T\).

The other three depend on the insertion order. The root is simply the first value inserted: inserting 1, 2, 3 gives root 1 with a chain to the right, while 2, 1, 3 gives root 2 with two children. These two trees also differ in preorder (1, 2, 3 against 2, 1, 3) and postorder (3, 2, 1 against 1, 3, 2), so none of them can be found from \(V\) alone.

Answer: A