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

Problem and examples

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.

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).

How it works

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.

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.

Implementation and efficiency

C implementation

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

int main() {
    TreeNode* root = createNode(10);
    printf("Root value is: %d\n", root->val);
    free(root);
    return 0;
}

C++ implementation

#include <iostream>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int value) : val(value), left(nullptr), right(nullptr) {}
};

int main() {
    TreeNode* root = new TreeNode(20);
    cout << "Root value is: " << root->val << endl;
    delete root;
    return 0;
}

Python implementation

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

if __name__ == '__main__':
    root = TreeNode(30)
    print(f"Root value is: {root.val}")

Java implementation

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int value) {
            this.val = value;
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(40);
        System.out.println("Root value is: " + root.val);
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

const root = new TreeNode(50);
console.log("Root value is:", root.val);

Go implementation

package main

import "fmt"

type TreeNode struct {
    val   int
    left  *TreeNode
    right *TreeNode
}

func main() {
    root := &TreeNode{val: 60}
    fmt.Println("Root value is:", root.val)
}

Rust implementation

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

fn main() {
    let root = TreeNode {
        val: 70,
        left: None,
        right: None,
    };
    println!("Root value is: {}", root.val);
}

Kotlin implementation

class TreeNode(var val_: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun main() {
    val root = TreeNode(80)
    println("Root value is: ${root.val_}")
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?

    init(_ val: Int) {
        self.val = val
    }
}

let root = TreeNode(90)
print("Root value is: \(root.val)")

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

const root = new TreeNode(100);
console.log("Root value is:", root.val);