chapter

Binary Trees: Properties and Traversals Short Notes for GATE DA

Binary Trees: Properties and Traversals short notes for GATE DA: 2 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice que

binary trees properties and traversals short notes

Quick Revision: Reconstruction Cheat Sheet

Reconstruction Cheat Sheet Given Traversals Unique? Condition In-order + Pre-order YES Always unique for any binary tree. In-order + Post-order YES Always unique for any binary tree. Pre-order + Post-order NO Ambiguous for general binary trees. Pre-order + Post-order YES ONLY if the tree is a Full Binary Tree . Key Anchors Pre-order: Root is at the start . Post-order: Root is at the end . In-order: The anchor that splits left and right subtrees.

Quick Revision: Structural Properties Cheat Sheet

Structural Properties Cheat Sheet General Binary Tree Total Nodes: N = L + I Leaves vs D-2: L = n_{2} + 1 Edge Eq: N - 1 = n_{1} + 2 n_{2} Max Height: H_{max} = N - 1 Min Height: H_{min} = ⌊ lo g_{2} N ⌋ Full Binary Tree (Strictly 0 or 2 children) Leaves vs Int: L = I + 1 Total (via L): N = 2 L - 1 Total (via I): N = 2 I + 1 Final Rule: Never apply Full Binary Tree formulas to a General Binary Tree unless explicitly stated.

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 short notes

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 Short Notes for GATE DA

Binary Trees: Properties and Traversals short notes for GATE DA: 2 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Quick Revision: Reconstruction Cheat Sheet

Reconstruction Cheat Sheet

Given Traversals	Unique?	Condition
In-order + Pre-order	YES	Always unique for any binary tree.
In-order + Post-order	YES	Always unique for any binary tree.
Pre-order + Post-order	NO	Ambiguous for general binary trees.
Pre-order + Post-order	YES	ONLY if the tree is a Full Binary Tree.

Key Anchors

Pre-order: Root is at the start.
Post-order: Root is at the end.
In-order: The anchor that splits left and right subtrees.

Quick Revision: Structural Properties Cheat Sheet

Structural Properties Cheat Sheet

General Binary Tree

Total Nodes: $N = L + I$
Leaves vs D-2: $L = n_{2} + 1$
Edge Eq: $N - 1 = n_{1} + 2 n_{2}$
Max Height: $H_{max} = N - 1$
Min Height: $H_{min} = ⌊ lo g_{2} N ⌋$

Full Binary Tree

(Strictly 0 or 2 children)

Leaves vs Int: $L = I + 1$
Total (via L): $N = 2 L - 1$
Total (via I): $N = 2 I + 1$

Final Rule: Never apply Full Binary Tree formulas to a General Binary Tree unless explicitly stated.

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$ .

binary trees properties and traversals short notes

Quick Revision: Reconstruction Cheat Sheet

Reconstruction Cheat Sheet

Key Anchors

Quick Revision: Structural Properties Cheat Sheet

Structural Properties Cheat Sheet

Try a question

Login to view the complete short notes

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 Short Notes for GATE DA

Quick Revision: Reconstruction Cheat Sheet

Reconstruction Cheat Sheet

Key Anchors

Quick Revision: Structural Properties Cheat Sheet

Structural Properties Cheat Sheet

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 short notes in this unit