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❯

Understanding the Problem

We are given a binary tree and our goal is to determine whether all the leaf nodes (nodes with no children) are located at the same level (i.e., same depth from the root).

For example, in the tree below:


       1
     /       2     3
   /         4         5

The leaves are nodes 4 and 5, and both are at level 2 (root is at level 0). Since all leaves are at the same level, the answer is true.

However, if the tree was:


       1
     /       2     3
   /       
  4         
 /           
6

Then, node 3 is a leaf at level 1, while node 6 is a leaf at level 3 — the leaf nodes are not at the same level, so the answer is false.

Step-by-Step Solution with Example

step 1: Choose a Traversal Strategy

To compare the levels of all leaf nodes, we can perform a level order traversal (Breadth-First Search), or a depth-first traversal with depth tracking. We'll use DFS here, keeping track of the level of each leaf node.

step 2: Use a Helper Function to Traverse

We define a recursive function that receives the current node and its level. When it reaches a leaf node, it checks: - Is this the first leaf? Record its level. - Is this a later leaf? Check if its level matches the first leaf’s level.

step 3: Implementing with Example

Let's take the following binary tree:


       10
     /        5      20
          /          15    25

Leaves: 5, 15, 25 — all are at level 2. So the output is true.

Now, if node 5 had a left child:


       10
     /        5      20
   /      /    2     15    25

Leaf nodes: 2 (level 2), 15 (level 2), 25 (level 2) → still true.

But if node 2 had a child:


       10
     /        5      20
   /      /    2     15    25
 /
1

Now leaves: 1 (level 3), 15 (level 2), 25 (level 2) → not at same level → false.

step 4: Return True or False

We return true only if all leaf nodes encountered match the level of the first leaf node.

Edge Cases

Case 1: Empty Tree

If the tree is empty (i.e., root is null), then there are no leaf nodes. Since there's nothing to violate the rule, we return true.

Case 2: Tree with One Node

If the tree contains only the root node, then it's a leaf by itself. Since it’s the only leaf, the condition is trivially satisfied. Output: true.

Case 3: All Leaf Nodes at Same Level in Unbalanced Tree

Even if the tree structure is unbalanced, we return true if the leaf nodes all occur at the same level.

Case 4: Leaves at Different Levels

If we find any leaf at a different level than the others, we immediately return false.

Finally

This problem tests your understanding of tree traversal and level management. The key idea is to track the depth of all leaf nodes and ensure they are the same. It’s a common technique in problems related to balance and symmetry in binary trees. Edge cases like empty trees and single-node trees must be handled first to ensure correctness.

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

Comments

Loading comments...