Understanding the Problem
We are given a binary tree and our goal is to determine whether all the leaf nodes (nodes with no children) are located at the same level (i.e., same depth from the root).
For example, in the tree below:
1
/ 2 3
/ 4 5
The leaves are nodes 4 and 5, and both are at level 2 (root is at level 0). Since all leaves are at the same level, the answer is true
.
However, if the tree was:
1
/ 2 3
/
4
/
6
Then, node 3 is a leaf at level 1, while node 6 is a leaf at level 3 — the leaf nodes are not at the same level, so the answer is false
.
Step-by-Step Solution with Example
step 1: Choose a Traversal Strategy
To compare the levels of all leaf nodes, we can perform a level order traversal (Breadth-First Search), or a depth-first traversal with depth tracking.
We'll use DFS here, keeping track of the level of each leaf node.
step 2: Use a Helper Function to Traverse
We define a recursive function that receives the current node and its level. When it reaches a leaf node, it checks:
- Is this the first leaf? Record its level.
- Is this a later leaf? Check if its level matches the first leaf’s level.
step 3: Implementing with Example
Let's take the following binary tree:
10
/ 5 20
/ 15 25
Leaves: 5, 15, 25 — all are at level 2. So the output is true
.
Now, if node 5 had a left child:
10
/ 5 20
/ / 2 15 25
Leaf nodes: 2 (level 2), 15 (level 2), 25 (level 2) → still true
.
But if node 2 had a child:
10
/ 5 20
/ / 2 15 25
/
1
Now leaves: 1 (level 3), 15 (level 2), 25 (level 2) → not at same level → false
.
step 4: Return True or False
We return true
only if all leaf nodes encountered match the level of the first leaf node.
Edge Cases
Case 1: Empty Tree
If the tree is empty (i.e., root is null), then there are no leaf nodes. Since there's nothing to violate the rule, we return true
.
Case 2: Tree with One Node
If the tree contains only the root node, then it's a leaf by itself. Since it’s the only leaf, the condition is trivially satisfied. Output: true
.
Case 3: All Leaf Nodes at Same Level in Unbalanced Tree
Even if the tree structure is unbalanced, we return true
if the leaf nodes all occur at the same level.
Case 4: Leaves at Different Levels
If we find any leaf at a different level than the others, we immediately return false
.
Finally
This problem tests your understanding of tree traversal and level management. The key idea is to track the depth of all leaf nodes and ensure they are the same.
It’s a common technique in problems related to balance and symmetry in binary trees. Edge cases like empty trees and single-node trees must be handled first to ensure correctness.
Comments
Loading comments...