Binary TreesProblem 23 of 35
Check if all leaf nodes are at same level or not
Problem Statement
Given a binary tree, check if all leaf nodes are at the same level.
Example 1:
12
/ \
5 7
/ \
3 1
Output: true
All leaves (3, 1) are at level 3
Example 2:
12
/ \
5 7
/
3
Output: false
Leaf 3 is at level 3, leaf 7 is at level 2
Approach 1: Brute Force (Store All Leaf Levels)
Intuition
Traverse the tree and store the level of each leaf node in a list. After traversal, check if all levels in the list are the same.
Algorithm
- Perform DFS traversal with level tracking
- When a leaf node is found, store its level in a list
- After traversal, verify all levels in list are equal
- Return true if all same, false otherwise
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private void findLeafLevels(TreeNode root, int level, List<Integer> levels) {
if (root == null) return;
// Check if leaf node
if (root.left == null && root.right == null) {
levels.add(level);
return;
}
// Traverse children
findLeafLevels(root.left, level + 1, levels);
findLeafLevels(root.right, level + 1, levels);
}
public boolean checkLeafLevelBruteForce(TreeNode root) {
if (root == null) return true;
List<Integer> levels = new ArrayList<>();
findLeafLevels(root, 0, levels);
// Check if all levels are same
for (int i = 1; i < levels.size(); i++) {
if (!levels.get(i).equals(levels.get(0))) {
return false;
}
}
return true;
}
}Complexity Analysis
- Time Complexity: O(n) - Visit each node once
- Space Complexity: O(n) - Store levels for all leaf nodes
Approach 2: Optimal (Store First Leaf Level Only)
Intuition
Instead of storing all leaf levels, just store the first leaf level encountered. For subsequent leaves, compare their level with the stored level. If any mismatch is found, return false immediately.
Algorithm
- Keep track of the first leaf level found
- For each leaf, compare its level with the first leaf level
- If mismatch found, set result to false and stop
- Return the result
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private int leafLevel = -1; // -1 means not yet found
private boolean result = true;
private void checkLeaves(TreeNode root, int level) {
if (root == null || !result) return;
// Check if leaf node
if (root.left == null && root.right == null) {
if (leafLevel == -1) {
// First leaf found, store its level
leafLevel = level;
} else if (leafLevel != level) {
// Level mismatch
result = false;
}
return;
}
// Traverse children
checkLeaves(root.left, level + 1);
checkLeaves(root.right, level + 1);
}
public boolean checkLeafLevel(TreeNode root) {
leafLevel = -1;
result = true;
checkLeaves(root, 0);
return result;
}
}Alternative: Using BFS (Level Order)
Complexity Analysis
- Time Complexity: O(n) - Visit each node once (can exit early on mismatch)
- Space Complexity: O(h) - Recursion stack depth, where h is height of tree
Key Takeaways
- Early termination: Stop as soon as a mismatch is found
- Store only necessary info: First leaf level is enough, no need to store all
- Both DFS and BFS work: DFS has better space for balanced trees, BFS traverses level by level
- Level tracking: Pass level as parameter in recursion
- This pattern applies to: Any "check property at specific level" problems