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

Contents

ProblemExamplesSolutionAlgorithmCode

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❯

  1. Given a binary tree, if the tree is empty, return true.
  2. Initialize a queue and enqueue the root node along with its level (0).
  3. Initialize a variable leafLevel to -1 to record the level of the first encountered leaf node.
  4. While the queue is not empty, dequeue a node along with its level.
  5. If the dequeued node is a leaf (i.e. has no left and right children), then:
    1. If leafLevel is -1, set it to the current level.
    2. Otherwise, if the current level does not equal leafLevel, return false.
  6. If the node is not a leaf, enqueue its non-null children with level incremented by 1.
  7. After processing all nodes, return true as all leaves are at the same level.

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
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))