Binary Trees, Binary Search Trees and Traversals Practice Questions for GATE CS

Solve 127+ Binary Trees, Binary Search Trees and Traversals practice questions for GATE CS with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Trees and Traversals

Chapter Roadmap

1. Binary Tree Structure, Height and Node Counts

Foundational properties, node relationships, height bounds, and pointer math.

2. Binary Search Tree Construction and Ordering

Insertion logic, search paths, and the strict left-smaller, right-larger invariant.

3. Tree Traversals and Recursive Processing

Inorder, preorder, postorder, level-order, and reconstructing trees.

4. Complete BSTs in Array Representation

Mapping tree nodes to array indices, heap properties, and memory optimization.

Goal: Transition from visual, pointer-based thinking to rigorous mathematical problem-solving.

The Binary Tree: Core Definition

A binary tree is a finite set of nodes that is either empty or consists of a root node and two disjoint subsets called the left subtree and right subtree.

Key Characteristics

Maximum Degree: Every node can have at most 2 children (degree 0, 1, or 2).
Ordered Subtrees: The left and right children are distinct. A tree with a single left child is structurally different from a tree with a single right child.

Note: This ordered nature is what allows binary trees to be used for searching and sorting later in the chapter.

Binary Trees, Binary Search Trees and Traversals: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Programming and Data Structures MCQ

In a binary search tree, let $X$ be an internal node, $Y$ be its immediate left child, and $Z$ be its immediate right child. Assuming all keys are distinct, which of the following represents the correct ascending order of their values?

A.
$Z < X < Y$
B.
$Y < X < Z$
C.
$X < Y < Z$
D.
$Y < Z < X$

Correct Answer:

Step-by-Step Solution

Key idea: This is a language-to-math translation question testing the strict definition of the BST invariant.

Step 1: Translate the BST property into mathematical inequalities. For any node $X$ , all values in its left subtree must be strictly less than $X$ . Therefore, $Y < X$ .

Step 2: Similarly, all values in the right subtree must be strictly greater than $X$ . Therefore, $X < Z$ .

Step 3: Combine the inequalities: $Y < X$ and $X < Z$ gives $Y < X < Z$ .

Step 4: Match this with the options. Option B matches exactly.

Answer: B

Question 2 · Programming and Data Structures MCQ

In a binary tree, if the number of nodes with exactly two children is 14, what is the number of leaf nodes?

A.
13
B.
14
C.
15
D.
28

Correct Answer:

Step-by-Step Solution

Insight: The number of leaf nodes ( $N_{0}$ ) in any binary tree is always exactly one more than the number of nodes with two children ( $N_{2}$ ).

Exam route: Use the formula $N_{0} = N_{2} + 1$ . Given $N_{2} = 14$ , $N_{0} = 14 + 1 = 15$ .

Learning route:

Let $N_{0}$ be leaf nodes, $N_{1}$ be nodes with 1 child, $N_{2}$ be nodes with 2 children.
Total nodes $N = N_{0} + N_{1} + N_{2}$ .
Total edges $E = N - 1$ . Also, $E = N_{1} + 2 N_{2}$ (sum of children).
Equating them: $N_{0} + N_{1} + N_{2} - 1 = N_{1} + 2 N_{2}$ .
Simplifying gives $N_{0} = N_{2} + 1$ .

Verification: If $N_{2} = 14$ , then $N_{0} = 15$ . This holds regardless of $N_{1}$ .

Question 3 · Programming and Data Structures MCQ

The inorder traversal of a binary search tree (BST) visits the nodes in a specific order based on the BST property. Which of the following sequences is IMPOSSIBLE for the inorder traversal of a valid BST containing distinct integers?

A.
10, 20, 30, 40, 50
B.
-5, 0, 5, 10, 15
C.
50, 40, 30, 20, 10
D.
1, 2, 3, 4, 5

Correct Answer:

Step-by-Step Solution

Key idea: This is a boundary case question testing the fundamental consequence of the BST invariant on traversals.

Step 1: Recall the BST property: for any node, all values in the left subtree are smaller, and all values in the right subtree are larger.

Step 2: Recall how inorder traversal works: Left $\to$ Root $\to$ Right.

Step 3: Combine these two facts. Because we visit the smaller left subtree first, then the root, then the larger right subtree, the inorder traversal of a BST will ALWAYS produce a strictly sorted sequence in ascending order.

Step 4: Examine the options. Options A, B, and D are sorted in ascending order. Option C is sorted in descending order.

Answer: C

Question 4 · Programming and Data Structures MCQ

In a valid Binary Search Tree (BST), the root node contains the value 100. The left child of the root contains the value 40. Which of the following values can be the right child of the node containing 40?

A.
35
B.
55
C.
105
D.
145

Correct Answer:

Step-by-Step Solution

Key idea: This is a casework question testing the strict bounds imposed by the BST invariant on subtrees.

Step 1: Recall the BST invariant: for any node, all values in its left subtree must be strictly less than the node's value, and all values in its right subtree must be strictly greater.

Step 2: The node 40 is in the left subtree of the root (100). Therefore, all nodes in the subtree rooted at 40 must have values strictly less than 100.

Step 3: We are looking for the right child of 40. By the BST property, the right child of 40 must be strictly greater than 40.

Step 4: Combining these constraints, the value must be strictly greater than 40 AND strictly less than 100. That is, $40 < x < 100$ .

Step 5: Evaluate the options. 35 is $< 40$ . 105 and 145 are $> 100$ . Only 55 satisfies $40 < 55 < 100$ .

Answer: B

Question 5 · Programming and Data Structures MCQ

Consider the following statements regarding the inorder successor of a node $V$ in a Binary Search Tree (BST):

Assertion (A): The inorder successor of a node $V$ that has no right child is always its immediate parent.

Reason (R): The inorder successor is defined as the node that appears immediately after $V$ in the inorder traversal sequence.

Select the correct option from the following:

A.
Both A and R are true and R is the correct explanation of A.
B.
Both A and R are true but R is NOT the correct explanation of A.
C.
A is true but R is false.
D.
A is false but R is true.

Correct Answer:

Step-by-Step Solution

Key idea: This is a construction question testing the precise rules for finding the inorder successor when the right subtree is empty.

Step 1: Evaluate Reason (R). The inorder successor is indeed defined as the next node in the inorder traversal (Left $\to$ Root $\to$ Right). This statement is fundamentally true.

Step 2: Evaluate Assertion (A). If $V$ has no right child, its successor must be found by moving up the ancestors. The rule is: find the lowest ancestor for which $V$ is in the left subtree.

Step 3: Is this ancestor ALWAYS the immediate parent? No. If $V$ is the right child of its parent, then $V$ is NOT in the left subtree of its parent. In this case, you must continue moving up until you find an ancestor where you took a left turn.

Step 4: Therefore, Assertion (A) is false because it incorrectly restricts the successor to the immediate parent in all cases.

Step 5: Conclusion: A is false, but R is true.

Answer: D

Question 6 · Programming and Data Structures MCQ

The keys 50, 30, 70, 20, 40 are inserted in this order into an initially empty binary search tree. What is the value of the inorder successor of the node containing 30?

A.
20
B.
40
C.
50
D.
70

Correct Answer:

Step-by-Step Solution

Key idea: Inorder successor of a node with right child is the minimum of that right subtree.

Step 1: Build the BST by inserting keys in order: 50, 30, 70, 20, 40

Insert 50: Root = 50

```

Insert 30: 30 < 50, goes to left of 50

```

Insert 70: 70 > 50, goes to right of 50

```

/ \

30 70

```

Insert 20: 20 < 50 (left), 20 < 30 (left)

```

/ \

30 70

```

Insert 40: 40 < 50 (left), 40 > 30 (right)

```

/ \

30 70

/ \

20 40

```

Step 2: Find inorder successor of node 30

Node 30 has a right child (40).

Rule: When node has right child, successor = minimum of right subtree.

Right subtree of 30: {40}

Minimum of {40} = 40

Step 3: Therefore, inorder successor of 30 is 40.

Answer: 40 (Option B)

Question 7 · Programming and Data Structures MCQ

The keys 60, 40, 80, 30, 50, 70, 90 are inserted in this order into an initially empty binary search tree. What is the height of the resulting tree? (Height of a tree with only root is 0.)

A.
2
B.
3
C.
4
D.
7

Correct Answer:

Step-by-Step Solution

Key idea: Build the BST by inserting keys in order, then find the height (longest path from root to leaf).

Step 1: Insert 60. Root = 60.

```

Step 2: Insert 40. 40 < 60, goes to left.

```

Step 3: Insert 80. 80 > 60, goes to right.

```

/ \

40 80

```

Step 4: Insert 30. 30 < 60 (left), 30 < 40 (left).

```

/ \

40 80

```

Step 5: Insert 50. 50 < 60 (left), 50 > 40 (right).

```

/ \

40 80

/ \

30 50

```

Step 6: Insert 70. 70 > 60 (right), 70 < 80 (left).

```

/ \

40 80

/ \ /

30 50 70

```

Step 7: Insert 90. 90 > 60 (right), 90 > 80 (right).

```

/ \

40 80

/ \ / \

30 50 70 90

```

Step 8: Find height. Height = longest path from root to leaf.

Path to 30: 60 → 40 → 30 (2 edges)
Path to 50: 60 → 40 → 50 (2 edges)
Path to 70: 60 → 80 → 70 (2 edges)
Path to 90: 60 → 80 → 90 (2 edges)

Maximum path length = 2 edges.

Answer: Height = 2 (Option A)

Question 8 · Programming and Data Structures MCQ

A binary tree has the following preorder traversal: 10, 5, 2, 7, 15, 12, 20.

Its inorder traversal is: 2, 5, 7, 10, 12, 15, 20.

What is the value of the right child of the root's right child?

A.
20
B.
12
C.
15
D.
NULL

Correct Answer:

Step-by-Step Solution

Key idea: Use the preorder traversal to identify the root, then use the inorder traversal to split the tree into left and right subtrees. Repeat recursively.

Step 1: Identify the root of the entire tree.

Preorder starts with the root. So, Root = 10.

Step 2: Split the inorder traversal using the root.

Inorder: 2, 5, 7, [10], 12, 15, 20.

Left subtree inorder: 2, 5, 7.

Right subtree inorder: 12, 15, 20.

Step 3: Identify the right subtree's preorder.

The right subtree has 3 nodes. In preorder, after the root (10) and the left subtree nodes (5, 2, 7), the next 3 nodes belong to the right subtree.

Right subtree preorder: 15, 12, 20.

Step 4: Analyze the right subtree.

Root of right subtree = first element of its preorder = 15.

So, the root's right child is 15.

Step 5: Split the right subtree's inorder using its root (15).

Right subtree inorder: 12, [15], 20.

Left child of 15: 12.

Right child of 15: 20.

Step 6: Answer the specific question.

The question asks for the right child of the root's right child.

Root's right child = 15.

Right child of 15 = 20.

Answer: 20 (Option A)

Question 9 · Programming and Data Structures MCQ

Which of the following statements is TRUE for a strict (full) binary tree with $n$ nodes?

A.
The number of leaf nodes is exactly $r a c n + 1 2$
B.
The number of leaf nodes is exactly $r a c n 2$
C.
The number of nodes with one child is $r a c n - 1 2$
D.
The height is always $lo g_{2} n$

Correct Answer:

Step-by-Step Solution

Insight: In a strict binary tree, there are no nodes with exactly one child ( $N_{1} = 0$ ).

Exam route: $N = N_{0} + N_{2}$ . Since $N_{0} = N_{2} + 1$ , substitute $N_{2} = N_{0} - 1$ into the first equation: $N = N_{0} + (N_{0} - 1) = 2 N_{0} - 1$ . Solving for $N_{0}$ gives $N_{0} = \frac{n + 1}{2}$ .

Learning route:

A strict (full) binary tree has $N_{1} = 0$ .
Total nodes $n = N_{0} + N_{2}$ .
We know $N_{0} = N_{2} + 1$ , so $N_{2} = N_{0} - 1$ .
Substitute: $n = N_{0} + N_{0} - 1 = 2 N_{0} - 1$ .
Rearrange: $2 N_{0} = n + 1 ⟹ N_{0} = \frac{n + 1}{2}$ .

Verification: For $n = 3$ (root + 2 children), $N_{0} = (3 + 1) /2 = 2$ . Correct.

Question 10 · Programming and Data Structures MCQ

An initially empty binary search tree contains 100 distinct integers. What is the minimum possible number of comparisons required to insert a new, distinct integer into this tree?

A.
1
B.
7
C.
50
D.
100

Correct Answer:

Step-by-Step Solution

Key idea: This is a comparison question testing the best-case scenario for the BST insertion algorithm.

Step 1: Recall the standard insertion algorithm. We start at the root, compare the new value with the current node, and move left or right until we find a null pointer.

Step 2: The number of comparisons equals the number of nodes visited (including the root) before finding the null pointer.

Step 3: To minimize comparisons, we want to find a null pointer as quickly as possible. The fastest way is if the new node is inserted as a direct child of the root.

Step 4: Inserting as a child of the root requires exactly 1 comparison (with the root itself). The tree having 100 nodes does not prevent the root from having an empty child spot.

Answer: A

Try a question

Login to view the complete practice questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Binary Trees, Binary Search Trees and Traversals Practice Questions for GATE CS

Chapter Roadmap: Trees and Traversals

Chapter Roadmap

The Binary Tree: Core Definition

The Binary Tree: Core Definition

Key Characteristics

Binary Trees, Binary Search Trees and Traversals: Solved Questions with Step-by-Step Explanations (10 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More practice questions in this unit