Check if All Leaves are at Same Level — Problem & Solution
Check if All Leaves are at Same Level solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Check if All Leaves are at Same Level is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon and Paytm interviews.
- Difficulty: Easy
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Paytm
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, return true if all of its leaves (nodes with no children) are at the same depth, and false otherwise.
Example 1
Input: root = [1,2,3]
Output: true
Explanation: Both leaves, 2 and 3, are one level below the root.
Example 2
Input: root = [10,20,30,10,15]
Output: false
Explanation: The leaves 10 and 15 are two levels down, but the leaf 30 is only one.
Example 3
Input: root = [7,3,null,null,1]
Output: true
Explanation: The tree is a path, so its single leaf is trivially level with itself.
Constraints
1 <= number of nodes <= 10^51 <= Node.val <= 10^5
Hints for Check if All Leaves are at Same Level
Hint 1
Only the depths of the leaves matter.
Hint 2
Traverse the tree carrying the current depth; the first leaf you meet fixes the depth every other leaf must have.
Hint 3
Return
falseas soon as a leaf at a different depth turns up.
How to solve Check if All Leaves are at Same Level
Record the depth of the first leaf the traversal reaches, then require every later leaf to match it.
Approach
- Set
leafDepth = -1(no leaf seen yet). - Traverse the tree depth-first, passing each node its depth.
- At a leaf: if
leafDepthis -1, set it to this depth; otherwise, if the depths differ, the answer isfalse. - If the traversal finishes, return
true.
Why it works
All leaves are at one depth exactly when each of them equals the depth of any one of them — the first one found serves as that reference.
Complexity
- Time —
O(n) - Space —
O(h) for the recursion (or O(w) with a level-order traversal)
Pitfalls
- A node with one child is not a leaf, even though one side is empty.
- A level-order variant works too: once a level contains a leaf, it must be the last level.
Reference solution
Python
from typing import Optional
def check(root: Optional[TreeNode]) -> bool:
leaf_depth = -1
stack = [(root, 0)]
while stack:
node, depth = stack.pop()
if node.left is None and node.right is None:
if leaf_depth < 0:
leaf_depth = depth
elif depth != leaf_depth:
return False
if node.left:
stack.append((node.left, depth + 1))
if node.right:
stack.append((node.right, depth + 1))
return TrueJava
public static boolean check(TreeNode root) {
int[] leafDepth = { -1 };
return sameLevel(root, 0, leafDepth);
}
static boolean sameLevel(TreeNode node, int depth, int[] leafDepth) {
if (node == null) return true;
if (node.left == null && node.right == null) {
if (leafDepth[0] < 0) leafDepth[0] = depth;
return leafDepth[0] == depth;
}
return sameLevel(node.left, depth + 1, leafDepth) && sameLevel(node.right, depth + 1, leafDepth);
}C++
bool sameLevel(TreeNode* node, int depth, int& leafDepth);
bool check(TreeNode* root) {
int leafDepth = -1;
return sameLevel(root, 0, leafDepth);
}
bool sameLevel(TreeNode* node, int depth, int& leafDepth) {
if (!node) return true;
if (!node->left && !node->right) {
if (leafDepth < 0) leafDepth = depth;
return leafDepth == depth;
}
return sameLevel(node->left, depth + 1, leafDepth) && sameLevel(node->right, depth + 1, leafDepth);
}JavaScript
var check = function(root) {
var leafDepth = -1;
var stack = [[root, 0]];
while (stack.length > 0) {
var top = stack.pop(), node = top[0], depth = top[1];
if (node.left === null && node.right === null) {
if (leafDepth < 0) leafDepth = depth;
else if (depth !== leafDepth) return false;
}
if (node.left !== null) stack.push([node.left, depth + 1]);
if (node.right !== null) stack.push([node.right, depth + 1]);
}
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)