Check if All Leaf Nodes are at the Same Level in a Binary Tree

Problem Statement❯

Given a binary tree, determine if all its leaf nodes (nodes with no children) are present at the same level. Return true if they are, otherwise return false.

Examples❯

Input Tree	All Leaves Same Level?	Description
[1, 2, 3, 4, 5, null, null]	false	Leaf 3 is at level 2; leaves 4 and 5 are at level 3 — not the same.
[1, 2, 3, null, 4]	false	Leaf 3 is at level 2; leaf 4 is at level 3 — different levels.
[7]	true	Only one node, which is also a leaf — trivially same level.
[]	true	No nodes means no leaf nodes — considered valid by default.
[1, 2, null, 3, null, 4]	true	Only one leaf (node 4) exists — all leaves are at the same level.
[10, 20, 30, 40, 50, 60, 70]	true	All leaf nodes (40, 50, 60, 70) are at the same level (level 3).

Solution❯

Case 1: Empty Tree

If the binary tree has no nodes (i.e. it's null), then there are no leaf nodes. In this situation, we consider all leaf nodes to be at the same level by definition. Hence, the answer is true.

Case 2: Tree with a Single Node

If there is only one node (the root), then it is also a leaf node. Since it's the only leaf, all leaves are clearly at the same level (level 0), so the answer is true.

Case 3: Perfectly Balanced Tree

If all paths from root to leaf have the same length, then all leaf nodes will be found at the same depth. For instance, in a complete binary tree with all levels filled, leaf nodes will all occur at the last level. This scenario returns true.

Case 4: Unbalanced Tree with Same-Level Leaves

Even in unbalanced trees, if the leaf nodes happen to be at the same depth (level), the function should return true. The structure of the tree doesn’t have to be symmetric; only the levels of leaf nodes matter.

Case 5: Unbalanced Tree with Different-Level Leaves

If the tree has leaf nodes at varying depths (i.e., one leaf is found at level 2, and another at level 3), then the answer must be false. This indicates that not all paths from root to leaf are the same length, violating the condition.

Algorithm Steps❯

Given a binary tree, if the tree is empty, return true.
Initialize a queue and enqueue the root node along with its level (0).
Initialize a variable leafLevel to -1 to record the level of the first encountered leaf node.
While the queue is not empty, dequeue a node along with its level.
If the dequeued node is a leaf (i.e. has no left and right children), then:

If leafLevel is -1, set it to the current level.
Otherwise, if the current level does not equal leafLevel, return false.

If the node is not a leaf, enqueue its non-null children with level incremented by 1.
After processing all nodes, return true as all leaves are at the same level.

Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

from collections import deque

def are_leaves_at_same_level(root):
    if not root:
        return True
    queue = deque([(root, 0)])
    leaf_level = -1
    while queue:
        node, level = queue.popleft()
        if not node.left and not node.right:
            if leaf_level == -1:
                leaf_level = level
            elif level != leaf_level:
                return False
        if node.left:
            queue.append((node.left, level + 1))
        if node.right:
            queue.append((node.right, level + 1))
    return True

# Example usage:
if __name__ == '__main__':
    # Construct binary tree:
    #         1
    #       /   \
    #      2     3
    #     / \     \
    #    4   5     6
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))
    print(are_leaves_at_same_level(root))

⬅ Previous TopicCheck if a Binary Tree is a Sum Tree

Next Topic ⮕Lowest Common Ancestor (LCA) in a Binary Tree