Binary Trees, Binary Search Trees and Traversals PYQs for GATE CS

Solve 13+ Binary Trees, Binary Search Trees and Traversals previous year 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 · 2026_Set2 MCQ

The set T represents various traversals over binary tree. The set S represents the order of visiting nodes during a traversal.

T	S
I: Inorder	L: left subtree, node, right subtree
II: Preorder	M: node, left subtree, right subtree
III: Postorder	N: left subtree, right subtree, node

Which one of the following is the correct match from T to S ?

A.
I – L, II – M, III – N
B.
I – M, II – L, III – N
C.
I – N, II – M, III – L
D.
I – L, II – N, III – M

Correct Answer:

Step-by-Step Solution

Insight: The names of the traversals (pre, in, post) directly indicate the position of the current node relative to its subtrees.

Exam route: Preorder = Node first (pre). Inorder = Node in the middle (in). Postorder = Node last (post). Match these to the given descriptions: I (Inorder) is L (left, node, right). II (Preorder) is M (node, left, right). III (Postorder) is N (left, right, node). This matches option A.

Learning route:

Depth-first traversals are defined by when the current node is processed relative to its left and right subtrees.
Preorder: The prefix "pre" means the node is visited before its subtrees. Order: Node, Left, Right (M).
Inorder: The prefix "in" means the node is visited in between its left and right subtrees. Order: Left, Node, Right (L).
Postorder: The prefix "post" means the node is visited after both subtrees. Order: Left, Right, Node (N).
Matching these definitions to the given set S yields I-L, II-M, III-N.

Verification: Consider a tree with root A, left B, right C. Preorder visits A, then B, then C (Node, Left, Right). Inorder visits B, then A, then C (Left, Node, Right). Postorder visits B, then C, then A (Left, Right, Node). This perfectly matches M, L, N respectively.

Question 2 · Programming and Data Structures · 2026_Set2 MSQ

Consider a binary search tree (BST) with

n

leaf nodes (

n > 0

). Given any node

V

, the key present in the node is denoted as

V a l (V)

. All the keys present in the given BST are distinct. The keys belong to the set of real numbers.
For a node

V

, let

S u c (V)

denote the node that is its inorder successor. If a node

V

does not have an inorder successor, then

S u c (V)

N U LL

. As there are no duplicates, if

S u c (V)

is not

N U LL

, then

V a l (V) < V a l (S u c (V))

.

Corresponding to every leaf node

L_{i}

that has a non-NULL

S u c (L_{i})

, a new key

k_{i}

with the following property is to be inserted into the BST.

V a l (L_{i}) < k_{i} < V a l (S u c (L_{i}))

Let

K

represent the list of all such new keys to be inserted into the BST.

Which of the following statements is/are true?

A.
$K$ cannot have any duplicates
B.
$K$ will have at least one element
C.
After inserting all keys from $K$ , the height of the BST can increase at most by one
D.
Number of nodes in the BST will double after inserting all keys from $K$

Correct Answer:

["A","C"]

Step-by-Step Solution

Insight: This is a BST structural property question, recognizable because it asks about the effect of inserting keys between a leaf and its inorder successor.

Exam route: The inorder successor of a leaf $L_{i}$ is the next node in sorted order. The interval $(V a l (L_{i}), V a l (S u c (L_{i})))$ contains no existing tree nodes. Inserting $k_{i}$ here always makes it the right child of $L_{i}$ . Since intervals for different leaves are disjoint, all $k_{i}$ are distinct (A is true). New nodes are added at depth $d e pt h (L_{i}) + 1 \leq H + 1$ , so height increases by at most 1 (C is true). If $n = 1$ , $K$ is empty (B is false). Total nodes become $N + ∣ K ∣$ , which does not double (D is false).

Learning route:

Step 1: Analyze the insertion point. For a leaf $L_{i}$ with a non-NULL successor, $S u c (L_{i})$ is the lowest ancestor of $L_{i}$ that is greater than $L_{i}$ . Any value $k_{i}$ strictly between them will follow the exact path to $L_{i}$ and then go right, becoming the right child of $L_{i}$ .

Step 2: Check for duplicates (Option A). In the sorted inorder sequence, $L_{i}$ and $S u c (L_{i})$ are adjacent in terms of the condition that no tree node lies between them. Thus, the open intervals $(V a l (L_{i}), V a l (S u c (L_{i})))$ for different leaves are strictly disjoint. Any chosen $k_{i}$ must be distinct. Option A is TRUE.

Step 3: Check for empty $K$ (Option B). If the tree has $n = 1$ node, it is a leaf, and its successor is NULL. Thus, $K$ is empty. Option B is FALSE.

Step 4: Check height increase (Option C). The original height is $H = max (d e pt h (L_{i}))$ . New nodes are added as right children of leaves, so their depth is $d e pt h (L_{i}) + 1 \leq H + 1$ . The height can increase by at most 1. Option C is TRUE.

Step 5: Check node doubling (Option D). We add at most $n - 1$ nodes. The new total is $N + n - 1$ . For this to equal $2 N$ , we would need $N = n - 1$ , which is impossible for any valid tree. Option D is FALSE.

Wrong path: Assuming $n > 1$ always, leading to the belief that $K$ must have at least one element. Or assuming "doubling" is possible by miscounting the number of leaves versus total nodes.

Question 3 · Programming and Data Structures · 2026_Set1 NAT

The height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree. The maximum possible height of a full binary tree with 23 nodes is _________. (answer in integer)

Correct Answer:

11.00

Step-by-Step Solution

Insight: This is a strict binary tree height question, recognizable because it asks for the "maximum possible height" of a "full" (strict) binary tree with a given node count.

Exam route: A full binary tree has nodes with 0 or 2 children. To maximize height, make the tree as unbalanced as possible: each internal node has one leaf child and one internal node child. The number of internal nodes is $(n - 1) /2$ . The max height equals the number of internal nodes. For $n = 23$ , height = $(23 - 1) /2 = 11$ .

Learning route:

Step 1: Understand the constraints. A "full" or "strict" binary tree requires every node to have either 0 or 2 children. No node can have exactly 1 child.

Step 2: Relate nodes to degrees. Let $N_{0}$ be leaves, $N_{2}$ be internal nodes (degree 2). We know $N_{0} = N_{2} + 1$ and Total $N = N_{0} + N_{2}$ .

Step 3: Calculate $N_{2}$ for $N = 23$ .

$23 = (N_{2} + 1) + N_{2} ⟹ 2 N_{2} = 22 ⟹ N_{2} = 11$ .

There are exactly 11 internal nodes.

Step 4: Maximize the height. Height is the number of edges on the longest root-to-leaf path. To make this path as long as possible, we must string the internal nodes together in a single "spine".

Step 5: Construct the spine. Each of the 11 internal nodes (except the last one) will have one child that is a leaf (which terminates that branch) and one child that is the next internal node in the spine. The 11th internal node will have two leaf children.

Step 6: Count the edges. The path from the root to the deepest leaf passes through all 11 internal nodes. The number of edges in this path is exactly 11.

Formula: $h_{ma x} = \frac{N - 1}{2} = \frac{23 - 1}{2} = 11$ .

Wrong path: Confusing "full" with "perfect". A perfect tree minimizes height ( $h = ⌊ lo g_{2} 23 ⌋ = 4$ ). The question asks for maximum height, which requires maximizing imbalance while respecting the strict degree constraint.

Question 4 · Programming and Data Structures · 2026_Set1 NAT

The following sequence corresponds to the preorder traversal of a binary search tree

T

50, 25, 13, 40, 30, 47, 75, 60, 70, 80, 77

The position of the element 60 in the postorder traversal of

T

is ______. (answer in integer)

Note: The position begins with 1.

Correct Answer:

7.00

Step-by-Step Solution

Insight: This is a BST reconstruction from preorder question, recognizable because it provides a preorder sequence and asks for the position of a specific node in the postorder sequence.

Exam route: Reconstruct the BST by splitting the preorder sequence at each root: elements smaller go left, larger go right. Once the tree is built, generate the postorder traversal (Left, Right, Root) and count the 1-based index of the target element.

Learning route:

Step 1: Reconstruct the BST from preorder: [50, 25, 13, 40, 30, 47, 75, 60, 70, 80, 77].

Root is 50.
Left subtree (values < 50): [25, 13, 40, 30, 47].
Root 25. Left: [13]. Right: [40, 30, 47].
Root 40. Left: [30]. Right: [47].
Right subtree (values > 50): [75, 60, 70, 80, 77].
Root 75. Left: [60, 70]. Right: [80, 77].
Root 60. Left: []. Right: [70].
Root 80. Left: [77]. Right: [].

Step 2: Verify the tree structure.

/ \

25 75

/ \ / \

13 40 60 80

/ \ \ /

30 47 70 77

Step 3: Generate postorder traversal (Left, Right, Root).

Left subtree of 50 (root 25): 13, (30, 47, 40), 25 $\to$ 13, 30, 47, 40, 25.
Right subtree of 50 (root 75): (70, 60), (77, 80), 75 $\to$ 70, 60, 77, 80, 75.
Root: 50.

Full postorder: 13, 30, 47, 40, 25, 70, 60, 77, 80, 75, 50.

Step 4: Find the position of 60.

Counting from 1: 13(1), 30(2), 47(3), 40(4), 25(5), 70(6), 60(7).

The position is 7.

Wrong path: Misplacing 70 as the left child of 80 (since 70 < 80), ignoring that 70 appeared before 80 in preorder and is > 60, so it must be in 60's subtree. This would shift the postorder sequence and the position of 60.

Question 5 · Programming and Data Structures · 2026_Set1 MCQ

Let

P

be the set of all integers from 1 to 15. Consider any order of insertion of the elements of

P

into a binary search tree that creates a complete binary tree.

Which one of the following elements can NEVER be the third element that is inserted?

A.
4
B.
2
C.
10
D.
5

Correct Answer:

Step-by-Step Solution

Insight: This is a BST construction constraint question, recognizable because it asks about the validity of a specific insertion order to achieve a rigid structural outcome (a complete binary tree).

Exam route: A complete BST of 1..15 has a fixed shape. The root must be the median (8). Its children must be the medians of the left (1..7 $\to$ 4) and right (9..15 $\to$ 12) subsets. The first three inserted elements must be the root and its two children (in some order: 8, then 4 and 12). The children of 4 are 2 and 6. The children of 12 are 10 and 14. Therefore, the 3rd element can only be 4, 12, 2, 6, 10, or 14. It cannot be 5.

Learning route:

Step 1: Understand the target structure. A complete binary tree with 15 nodes has 4 fully filled levels.

Step 2: Identify the root. To be complete and a valid BST, the root must be the median of the entire set ${1, \dots, 15}$ , which is 8. Thus, 8 must be the 1st element inserted.

Step 3: Identify the second level. The left subtree contains ${1, \dots, 7}$ and the right contains ${9, \dots, 15}$ . For these subtrees to be complete, their roots must be their respective medians: 4 and 12.

Step 4: Determine valid insertion orders. In BST insertion, a parent must be inserted before its children. Therefore, the first three elements inserted must be 8, followed by 4 and 12 in either order.

Step 5: Analyze the "3rd element" constraint. If the sequence starts with 8, 4, the 3rd element can be 12 (the other level-1 node), or 2 or 6 (children of 4). If it starts with 8, 12, the 3rd element can be 4, or 10 or 14 (children of 12).

Step 6: Evaluate the options. 4, 2, and 10 are all in the valid set of 3rd elements. 5 is a child of 6, meaning 6 must be inserted before 5. Thus, 5 cannot possibly be the 3rd element inserted.

Wrong path: Assuming any number smaller than 8 can be inserted early. If 5 is inserted 3rd, it would become a child of 4 (since 5 > 4), but in a complete BST, the right child of 4 must be 6 to maintain the complete structure of the left subtree. This breaks the completeness constraint.

Question 6 · Programming and Data Structures · 2025_Set2 NAT

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)

Correct Answer:

4.00

Step-by-Step Solution

Insight: This is a BST path length question, recognizable because it provides a specific insertion sequence and asks for the number of edges between a target node and the root.

Exam route: Construct the BST step-by-step using the given sequence. 10 is root. -4 is left of 10. 15 is right of 10. 30 is right of 15. 20 is left of 30. 5 is right of -4. 60 is right of 30. 19 is left of 20. The path from 19 to root is 19 $\to$ 20 $\to$ 30 $\to$ 15 $\to$ 10. Count the edges: 4.

Learning route:

Step 1: Initialize an empty BST.

Step 2: Insert 10. It becomes the root.

Step 3: Insert -4. $- 4 < 10$ , so it becomes the left child of 10.

Step 4: Insert 15. $15 > 10$ , so it becomes the right child of 10.

Step 5: Insert 30. $30 > 10$ (go right), $30 > 15$ (go right). It becomes the right child of 15.

Step 6: Insert 20. $20 > 10$ (right), $20 > 15$ (right), $20 < 30$ (left). It becomes the left child of 30.

Step 7: Insert 5. $5 < 10$ (left), $5 > - 4$ (right). It becomes the right child of -4.

Step 8: Insert 60. $60 > 10 \to 15 \to 30$ (all right). It becomes the right child of 30.

Step 9: Insert 19. $19 > 10$ (right), $19 > 15$ (right), $19 < 30$ (left), $19 < 20$ (left). It becomes the left child of 20.

Step 10: Trace the path from 19 to the root. The ancestors of 19 are 20, 30, 15, and 10.

Step 11: Count the edges in this path. 19 to 20 (1), 20 to 30 (2), 30 to 15 (3), 15 to 10 (4). Total edges = 4.

Wrong path: Counting the number of nodes in the path (5) instead of the number of edges (4), or incorrectly inserting 19 as a child of 15 or 30 directly, missing the intermediate node 20, leading to a path length of 3.

Question 7 · Programming and Data Structures · 2025_Set2 MCQ

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 nodes in

T

that have exactly two children?

A.
$\frac{n - 2}{2}$
B.
$\frac{n - 1}{2}$
C.
$\frac{n}{2}$
D.
$\frac{n + 1}{2}$

Correct Answer:

Step-by-Step Solution

Insight: This is a strict (full) binary tree property question, recognizable because it constrains every node to have exactly 0 or 2 children and asks for a node count formula.

Exam route: Use the fundamental identity $N_{0} = N_{2} + 1$ . Since it is a strict tree, $N_{1} = 0$ . Total nodes $n = N_{0} + N_{2}$ . Substitute $N_{0}$ to get $n = 2 N_{2} + 1$ . Solve for $N_{2}$ to get $(n - 1) /2$ .

Learning route:

Step 1: Define variables. Let $N_{0}$ be leaf nodes (0 children), $N_{1}$ be nodes with 1 child, and $N_{2}$ be nodes with 2 children.

Step 2: Apply the given constraint. Every node has 0 or 2 children, so $N_{1} = 0$ .

Step 3: State the total node equation. $n = N_{0} + N_{1} + N_{2} = N_{0} + N_{2}$ .

Step 4: Apply the universal binary tree edge property. Total edges = $n - 1$ . Also, total edges = $0 \cdot N_{0} + 1 \cdot N_{1} + 2 \cdot N_{2} = N_{1} + 2 N_{2}$ .

Step 5: Equate and substitute. $n - 1 = N_{1} + 2 N_{2}$ . Since $N_{1} = 0$ , we have $n - 1 = 2 N_{2}$ .

Step 6: Solve for $N_{2}$ . $N_{2} = \frac{n - 1}{2}$ .

Verification: If $n = 3$ (a root and two leaves), $N_{2} = (3 - 1) /2 = 1$ . This matches a root with two children.

Wrong path: Assuming $N_{0} = N_{2}$ , which leads to $n = 2 N_{2} ⟹ N_{2} = n /2$ (Option C), or assuming $N_{0} = N_{2} + 2$ , leading to $N_{2} = (n - 2) /2$ (Option A). These violate the fundamental edge-count derivation.

Question 8 · Programming and Data Structures · 2025_Set1 MSQ

Which of the following statement(s) is/are <b>TRUE</b> 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 (lo g_{2} n)$ time in the worst case.
D.
Every BST is also a Min-Heap.

Correct Answer:

["A","B"]

Step-by-Step Solution

Insight: A BST's inorder traversal is always sorted, and its maximum possible depth is $n - 1$ (achieved by a completely skewed tree).

Exam route: Evaluate each option. A is true because a tree with $n$ nodes has at most $n - 1$ edges in any path. B is true by the definition of BST. C is false because worst-case search is $O (n)$ for a skewed tree. D is false because BST ordering (left < parent < right) does not imply heap ordering (parent $\leq$ children).

Learning route:

Option A: A path in a tree with $n$ nodes can have at most $n$ nodes, which means $n - 1$ edges. A right-skewed BST achieves exactly this maximum length. Thus, the maximum length is bounded by and can be $n - 1$ .
Option B: The BST property (left subtree < node < right subtree) guarantees that an inorder traversal (Left, Node, Right) visits elements in strictly ascending order.
Option C: Search time is $O (h)$ , where $h$ is the height. In the worst case (skewed tree), $h = n - 1$ , making the time complexity $O (n)$ , not $O (lo g_{2} n)$ .
Option D: A Min-Heap requires every parent to be $\leq$ its children. A BST only requires left child < parent < right child. For example, a BST with root 10, left child 5, and right child 15 violates the Min-Heap property because 10 is not $\leq$ 5.

Verification: For $n = 3$ , elements ${1, 2, 3}$ inserted as $1, 2, 3$ gives a right-skewed tree. Path length from root (1) to leaf (3) is 2 edges ( $3 - 1 = 2$ ). Inorder is $1, 2, 3$ (sorted). Search for 3 takes 3 steps ( $O (n)$ ). Root 1 is not $\leq$ left child (none), but if we had root 2, left 1, right 3, 2 is not $\leq$ 1, so not a min-heap.

Question 9 · Programming and Data Structures · 2024_Set2 MCQ

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?

A.
Inorder traversal of $T$ can be determined from $V$
B.
Root node of $T$ can be determined from $V$
C.
Preorder traversal of $T$ can be determined from $V$
D.
Postorder traversal of $T$ can be determined from $V$

Correct Answer:

Step-by-Step Solution

Insight: Inorder traversal of any BST with distinct keys always yields the keys in sorted ascending order, regardless of the insertion sequence.

Exam route: The set $V$ contains all distinct elements. Sorting $V$ gives the unique inorder traversal. Root, preorder, and postorder depend on the unknown insertion order, so they cannot be determined. Thus, only inorder is determinable.

Learning route:

A BST enforces the invariant: for any node, all left descendants are smaller, and all right descendants are larger.
Inorder traversal visits Left, then Node, then Right.
By induction, this recursively guarantees that the output sequence is strictly sorted.
Since we are given the set $V$ , we can simply sort its elements to obtain this sequence.
The root is the first element inserted, which is unknown. Preorder and postorder depend on the tree structure, which varies with insertion order.

Verification: If $V = {2, 1, 3}$ , sorted $V$ is $1, 2, 3$ . Whether inserted as $(2, 1, 3)$ or $(1, 2, 3)$ , the inorder traversal is always $1, 2, 3$ .

Question 10 · Programming and Data Structures · 2023 MCQ

Consider the C function foo and the binary tree shown.

typedef struct node {
   int val;
   struct node *left, *right;
} node;

int foo(node *p) {
   int retval;
   if (p == NULL)
      return 0;
   else {
      retval = p->val + foo(p->left) + foo(p->right);
      printf("%d ", retval);
      return retval;
   }
}

When foo is called with a pointer to the root node of the given binary tree, what will it print?

A.
3 8 5 13 11 10
B.
3 5 8 10 11 13
C.
3 8 16 13 24 50
D.
3 16 8 50 24 13

Correct Answer:

Step-by-Step Solution

Insight: This is a recursive tree processing question, recognizable because the function makes recursive calls on left and right children before executing a print statement, indicating a post-order traversal with an accumulation operation.

Exam route: The function computes the sum of the subtree rooted at each node and prints it. Since the print happens after the recursive calls, it's a post-order traversal. Trace the tree bottom-up: leaves print their own values (3, 8, 13). Their parents print the sum of their subtrees (5+3+8=16, 11+0+13=24). The root prints the total sum (10+16+24=50). Output: 3, 8, 16, 13, 24, 50.

Learning route:

Step 1: Analyze the function foo. Base case: returns 0 for NULL. Recursive step: retval = p->val + foo(p->left) + foo(p->right). Action: printf("%d ", retval).

Step 2: Identify the traversal order. The action (print) occurs after both recursive calls. This is the definition of post-order traversal (Left, Right, Root).

Step 3: Identify the computed value. retval is the sum of the current node's value and the return values of its left and right subtrees. Thus, it prints the sum of each subtree.

Step 4: Trace the execution on the given tree.

foo(3): returns 3, prints 3.
foo(8): returns 8, prints 8.
foo(5): retval = 5 + 3 + 8 = 16. Prints 16, returns 16.
foo(NULL) (left of 11): returns 0.
foo(13): returns 13, prints 13.
foo(11): retval = 11 + 0 + 13 = 24. Prints 24, returns 24.
foo(10): retval = 10 + 16 + 24 = 50. Prints 50, returns 50.

Step 5: Collect the printed sequence: 3, 8, 16, 13, 24, 50.

Wrong path: Tracing the traversal order correctly (post-order) but forgetting that the function prints the accumulated sum (retval), not the original p->val. This leads to selecting the option that lists the raw node values in post-order (3, 8, 5, 13, 11, 10), which is Option A.

Try a question

Login to view the complete previous-year 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 PYQs 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 previous year questions (pyqs) in this unit