chapter

Binary Trees: Properties and Traversals Practice Questions for GATE DA

Solve 165+ Binary Trees: Properties and Traversals practice questions for GATE DA with answers and detailed solutions. Free sample questions below.

Try a question

Answer it here to see how it works. Nothing is recorded until you sign in.

Question 1

Level 1: Warm-up

What is the minimum number of nodes a general binary tree must have so that its Pre-order and Post-order traversals are ambiguous (i.e., more than one valid tree can be constructed)?

Question 2

Level 1: Warm-up

A student claims that Pre-order and Post-order traversals are sufficient to uniquely reconstruct any general binary tree. What is the minimum number of additional depth-first traversal sequences required to resolve this contradiction and guarantee unique reconstruction?

Question 3

Level 1: Warm-up

A general binary tree is uniquely determined by its Pre-order and Post-order traversals. What is the minimum number of children that every internal node in this tree must have?

Question 4

Level 1: Warm-up

Consider the following statements about reconstructing a binary tree from its Pre-order and Post-order traversals: (I) It is always possible to uniquely reconstruct any general binary tree. (II) It is possible to uniquely reconstruct a Full Binary Tree. Which of the statements is/are true?

Question 5

Level 1: Warm-up

What is the minimum number of distinct depth-first traversal sequences (chosen from Pre-order, In-order, and Post-order) required to uniquely reconstruct any general binary tree?

Question 6

Level 1: Warm-up

When reconstructing a binary tree from its Pre-order and In-order traversals, if the root is found at index k (0-indexed) in the In-order array, how many nodes are in the left subtree?

Question 7

Level 1: Warm-up

During the reconstruction of a binary tree from Pre-order and In-order traversals, the In-order sequence is split by the root into a left part of size L and a right part of size R . Which of the following correctly describes the split of the remaining Pre-order sequence?

Question 8

Level 1: Warm-up

When reconstructing a binary tree from its Post-order and In-order traversals, the In-order sequence is split by the root into a left part of size L and a right part of size R . If the Post-order array is 0-indexed, what is the index of the last element belonging to the Left Post-order subarray?

Question 9

Level 1: Warm-up

Consider the reconstruction of a binary tree from Pre-order and In-order traversals. Let the root be at index 0 in Pre-order and index k in In-order (0-indexed). Which of the following statements correctly identifies the index of the root of the right subtree in the Pre-order array?

Question 10

Level 1: Warm-up

In a binary tree reconstruction from Post-order and In-order traversals, the root is at the last index n - 1 of the Post-order array. If the In-order traversal places the root at index k (0-indexed), what is the 0-indexed starting position of the Right Post-order subarray?

Free preview ends here

Login to view the complete practice questions and solutions

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Binary Trees: Properties and Traversals Practice Questions for GATE DA

Solve 165+ Binary Trees: Properties and Traversals practice questions for GATE DA with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Binary Trees

Master the structural and navigational foundations of the most important tree data structure.

Your Learning Journey

1. Binary Tree Traversals and Reconstruction High Importance

Master pre-order, in-order, and post-order traversals.
Learn to uniquely reconstruct a tree from traversal sequences.
Understand the Full Binary Tree exception for pre-order and post-order.

2. Binary Tree Structural Properties Moderate Importance

Explore mathematical relationships between height, internal nodes, and leaves.
Derive bounds on the number of nodes for a given height.
Solve equations relating different tree parameters.

Binary Tree Traversals and Reconstruction

Master the art of rebuilding a tree from its shadows.

Chapter Context: Binary Trees: Properties and Traversals

What you will learn here

The core depth-first traversals (Pre-order, In-order, Post-order).
The mandatory role of In-order traversal in resolving left-right ambiguity.
Step-by-step methods to reconstruct a tree.
The Full Binary Tree exception for Pre-order and Post-order.

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

Question 1 · Programming, Data Structures and Algorithms MCQ

What is the minimum number of nodes a general binary tree must have so that its Pre-order and Post-order traversals are ambiguous (i.e., more than one valid tree can be constructed)?

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

Correct Answer:

Step-by-Step Solution

Key idea: Ambiguity in Pre-order and Post-order reconstruction occurs when a node has exactly one child, because the sequences cannot distinguish if it is a left or right child.

Step 1: For a tree with 1 node, Pre-order and Post-order are identical and uniquely define the tree.

Step 2: For a tree with 2 nodes (a root and one child), Pre-order is [Root, Child] and Post-order is [Child, Root]. The child could be either the left or right child of the root. This creates ambiguity.

Step 3: Therefore, the minimum number of nodes required to create this ambiguity is 2.

Answer: The minimum number of nodes is 2.

Question 2 · Programming, Data Structures and Algorithms MCQ

A student claims that Pre-order and Post-order traversals are sufficient to uniquely reconstruct any general binary tree. What is the minimum number of additional depth-first traversal sequences required to resolve this contradiction and guarantee unique reconstruction?

A.
0
B.
1
C.
2
D.
3

Correct Answer:

Step-by-Step Solution

Key idea: Pre-order and Post-order are ambiguous for general binary trees because they cannot distinguish left from right when a node has a single child.

Step 1: To resolve this ambiguity, the In-order traversal is mandatory because it explicitly separates left and right subtrees.

Step 2: The student already has Pre-order and Post-order. They only need to add the In-order traversal.

Step 3: Therefore, the minimum number of additional sequences required is exactly 1 (the In-order traversal).

Answer: The minimum number of additional sequences is 1.

Question 3 · Programming, Data Structures and Algorithms MCQ

A general binary tree is uniquely determined by its Pre-order and Post-order traversals. What is the minimum number of children that every internal node in this tree must have?

A.
0
B.
1
C.
2
D.
3

Correct Answer:

Step-by-Step Solution

Key idea: Pre-order and Post-order traversals are ambiguous for general binary trees if any node has exactly one child, because the sequences cannot distinguish whether that child is on the left or the right.

Step 1: For the tree to be uniquely reconstructed from Pre-order and Post-order alone, this ambiguity must not exist.

Step 2: The ambiguity only disappears if no node has exactly one child.

Step 3: Since internal nodes must have at least one child, and they cannot have exactly one child, every internal node must have exactly 2 children.

Step 4: This defines a Full Binary Tree.

Answer: Every internal node must have 2 children.

Question 4 · Programming, Data Structures and Algorithms MCQ

Consider the following statements about reconstructing a binary tree from its Pre-order and Post-order traversals:

(I) It is always possible to uniquely reconstruct any general binary tree.

(II) It is possible to uniquely reconstruct a Full Binary Tree.

Which of the statements is/are true?

A.
I only
B.
II only
C.
Both I and II
D.
Neither I nor II

Correct Answer:

Step-by-Step Solution

Key idea: This is a statement truth question testing the ambiguity trap of Pre-order and Post-order traversals.

Step 1: Evaluate Statement (I). Pre-order and Post-order can identify the root, but they cannot distinguish between a left child and a right child if a node has only one child. Therefore, reconstruction is ambiguous for general binary trees. Statement (I) is False.

Step 2: Evaluate Statement (II). A Full Binary Tree has no nodes with exactly one child. Because the ambiguity only arises from single-child nodes, Pre-order and Post-order are sufficient to uniquely reconstruct a Full Binary Tree. Statement (II) is True.

Step 3: Only Statement (II) is true.

Answer: II only.

Question 5 · Programming, Data Structures and Algorithms MCQ

What is the minimum number of distinct depth-first traversal sequences (chosen from Pre-order, In-order, and Post-order) required to uniquely reconstruct any general binary tree?

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

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct application of the golden rule of reconstruction.

Step 1: A single traversal (Pre, In, or Post alone) is never sufficient to uniquely reconstruct a general binary tree.

Step 2: Pre-order + Post-order is ambiguous for general trees (single-child ambiguity).

Step 3: In-order + Pre-order is always unique. In-order + Post-order is always unique.

Step 4: Therefore, exactly 2 traversals are sufficient, provided one of them is In-order.

Step 5: Since the question asks for the minimum number of distinct sequences, the answer is 2.

Answer: The minimum number is 2.

Question 6 · Programming, Data Structures and Algorithms MCQ

When reconstructing a binary tree from its Pre-order and In-order traversals, if the root is found at index $k$ (0-indexed) in the In-order array, how many nodes are in the left subtree?

A.
$k - 1$
B.
$k$
C.
$k + 1$
D.
$n - k$

Correct Answer:

Step-by-Step Solution

Key idea: In-order traversal visits the Left subtree, then the Root, then the Right subtree.

Step 1: The In-order array is structured as [Left Subtree Elements] + [Root] + [Right Subtree Elements].

Step 2: If the Root is at index $k$ (0-indexed), there are exactly $k$ elements before it.

Step 3: All elements before the root in the In-order sequence belong to the left subtree.

Answer: The number of nodes in the left subtree is $k$ .

Question 7 · Programming, Data Structures and Algorithms MCQ

During the reconstruction of a binary tree from Pre-order and In-order traversals, the In-order sequence is split by the root into a left part of size $L$ and a right part of size $R$ . Which of the following correctly describes the split of the remaining Pre-order sequence?

A.
The first $R$ elements form the Left Pre-order.
B.
The next $L$ elements form the Left Pre-order.
C.
The last $L$ elements form the Left Pre-order.
D.
The sequence is always split exactly in half.

Correct Answer:

Step-by-Step Solution

Key idea: Pre-order traversal visits the Root, then the Left subtree, then the Right subtree.

Step 1: The first element in the Pre-order array is the Root.

Step 2: The remaining elements consist of the Left Pre-order followed by the Right Pre-order.

Step 3: Since the left subtree has exactly $L$ nodes (determined from the In-order split), the next $L$ elements in the Pre-order array must belong to the left subtree.

Step 4: The remaining $R$ elements form the Right Pre-order.

Answer: The next $L$ elements form the Left Pre-order.

Question 8 · Programming, Data Structures and Algorithms MCQ

When reconstructing a binary tree from its Post-order and In-order traversals, the In-order sequence is split by the root into a left part of size $L$ and a right part of size $R$ . If the Post-order array is 0-indexed, what is the index of the last element belonging to the Left Post-order subarray?

A.
$L - 1$
B.
$L$
C.
$R - 1$
D.
$n - R$

Correct Answer:

Step-by-Step Solution

Key idea: Post-order traversal visits the Left subtree, then the Right subtree, then the Root.

Step 1: The Post-order array is structured as [Left Post-order] + [Right Post-order] + [Root].

Step 2: The Left Post-order subarray contains exactly $L$ elements.

Step 3: Since the array is 0-indexed, the first $L$ elements occupy indices $0, 1, \dots, L - 1$ .

Step 4: Therefore, the last element of the Left Post-order subarray is at index $L - 1$ .

Answer: The index is $L - 1$ .

Question 9 · Programming, Data Structures and Algorithms MCQ

Consider the reconstruction of a binary tree from Pre-order and In-order traversals. Let the root be at index 0 in Pre-order and index $k$ in In-order (0-indexed). Which of the following statements correctly identifies the index of the root of the right subtree in the Pre-order array?

A.
It is exactly $k + 1$ .
B.
It is exactly $k$ .
C.
It is bounded by $k \leq e x t in d e x \leq n - 1$ .
D.
It is exactly $n - k$ .

Correct Answer:

Step-by-Step Solution

Key idea: Pre-order traversal visits the Root, then the Left subtree, then the Right subtree.

Step 1: The root is at index 0 in the Pre-order array.

Step 2: The root is at index $k$ in the In-order array, which means there are exactly $k$ nodes in the left subtree.

Step 3: In the Pre-order array, the next $k$ elements (indices 1 to $k$ ) must belong to the left subtree.

Step 4: The element immediately following the left subtree's elements is the root of the right subtree.

Step 5: Its index is exactly $k + 1$ .

Answer: The index is exactly $k + 1$ .

Question 10 · Programming, Data Structures and Algorithms MCQ

In a binary tree reconstruction from Post-order and In-order traversals, the root is at the last index $n - 1$ of the Post-order array. If the In-order traversal places the root at index $k$ (0-indexed), what is the 0-indexed starting position of the Right Post-order subarray?

A.
$k$
B.
$k + 1$
C.
$n - k - 1$
D.
$n - k$

Correct Answer:

Step-by-Step Solution

Key idea: Post-order traversal visits the Left subtree, then the Right subtree, then the Root.

Step 1: The root is at index $k$ in the In-order array, which means there are exactly $k$ nodes in the left subtree.

Step 2: In the Post-order array, the first $k$ elements must belong to the Left Post-order subarray.

Step 3: Since the array is 0-indexed, the Left Post-order subarray occupies indices $0, 1, \dots, k - 1$ .

Step 4: The Right Post-order subarray begins immediately after the left subarray ends.

Step 5: Therefore, its starting index is exactly $k$ .

Answer: The starting position is $k$ .

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: Properties and Traversals Practice Questions for GATE DA

Chapter Roadmap: Binary Trees

Chapter Roadmap: Binary Trees

Your Learning Journey

Binary Tree Traversals and Reconstruction

Binary Tree Traversals and Reconstruction

What you will learn here

Binary Trees: Properties 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