Check if All Leaves are at Same Level

Easy
1893.

Check if All Leaves are at Same Level

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.

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^5
  • 1 <= Node.val <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var check = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^5
  • 1 <= Node.val <= 10^5

Hints for Check if All Leaves are at Same Level

  1. Hint 1

    Only the depths of the leaves matter.

  2. Hint 2

    Traverse the tree carrying the current depth; the first leaf you meet fixes the depth every other leaf must have.

  3. Hint 3

    Return false as 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

  1. Set leafDepth = -1 (no leaf seen yet).
  2. Traverse the tree depth-first, passing each node its depth.
  3. At a leaf: if leafDepth is -1, set it to this depth; otherwise, if the depths differ, the answer is false.
  4. 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 True

Java

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)