Binary Trees: Properties and Traversals Notes for GATE DA
Binary Trees: Properties and Traversals notes for GATE DA: 18 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice question
binary trees properties and traversals notes
Chapter Roadmap: Binary Trees
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 ReconstructionHigh 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 PropertiesModerate 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
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.
The Three Depth-First Traversals
The Three Depth-First Traversals
The order in which we visit the root determines the name of the traversal.
Traversal
Order of Visits
Mnemonic
Pre-order
Root, Left, Right
Prefix (Root comes first)
In-order
Left, Root, Right
Infix (Root is in the middle)
Post-order
Left, Right, Root
Postfix (Root comes last)
Key Insight: In-order traversal always visits the nodes in their natural left-to-right spatial order. This is why it is the most critical sequence for reconstruction.
15 more cards in this chapter
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 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.
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.
Binary Trees: Properties and Traversals Notes for GATE DA
Binary Trees: Properties and Traversals notes for GATE DA: 18 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.
Chapter Roadmap: Binary Trees
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 ReconstructionHigh 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 PropertiesModerate 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
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.
The Three Depth-First Traversals
The Three Depth-First Traversals
The order in which we visit the root determines the name of the traversal.
Traversal
Order of Visits
Mnemonic
Pre-order
Root, Left, Right
Prefix (Root comes first)
In-order
Left, Root, Right
Infix (Root is in the middle)
Post-order
Left, Right, Root
Postfix (Root comes last)
Key Insight: In-order traversal always visits the nodes in their natural left-to-right spatial order. This is why it is the most critical sequence for reconstruction.
The Golden Rule of Reconstruction
The Golden Rule of Reconstruction
To uniquely build a general binary tree, you MUST know the In-order traversal.
Why is In-order mandatory?
Pre-order and Post-order can identify the root of a tree.
However, they cannot distinguish between a left child and a right child if a node has only one child.
In-order resolves this ambiguity by explicitly separating the left subtree elements from the right subtree elements.
Core Principle: In-order is the anchor. Without it, the left-right spatial structure of the tree is lost.
Binary Trees: Properties and Traversals: Solved Questions with Step-by-Step Explanations (10 Problems)
Question 1 · Programming, Data Structures and AlgorithmsMCQ
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:
B
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 AlgorithmsMCQ
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:
B
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 AlgorithmsMCQ
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:
C
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 AlgorithmsMCQ
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:
B
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 AlgorithmsMCQ
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:
A
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 AlgorithmsMCQ
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:
B
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 AlgorithmsMCQ
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:
B
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 AlgorithmsMCQ
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:
A
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,…,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 AlgorithmsMCQ
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≤extindex≤n−1.
D.
It is exactly n−k.
Correct Answer:
A
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 AlgorithmsMCQ
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:
A
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,…,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.