Problem statement

Given the root of a binary tree, find the shallowest level that contains at least one leaf (a node with no children) and return the sum of the values of all the leaves on that level.

The root is on level 1. Return 0 for an empty tree.

Example 1

Input: root = [1,2,3,4,5,8,7,2]
Output: 20
Explanation: Level 3 is the first level holding leaves: 5, 8 and 7 (4 still has a child), so the sum is 20. The leaf 2 sits a level lower and is ignored.

Example 2

Input: root = [1,2,3,null,null,4,5,8,7]
Output: 2
Explanation: 2 is a leaf on level 2, the shallowest level with a leaf, and the only leaf there.

Example 3

Input: root = [6]
Output: 6
Explanation: The root alone is a leaf.

Constraints

• 0 <= number of nodes <= 10^3
• 1 <= Node.val <= 10^3

Hints for Sum of Leaf Nodes at Minimum Level

1. Hint 1

   The answer only concerns one level: the first one, from the top, that has a leaf.

2. Hint 2

   Walk the tree level by level (breadth-first) so that levels are met in order of depth.

3. Hint 3

   On each level add up the values of the nodes with no children; as soon as a level produced any, return its sum without going deeper.

How to solve Sum of Leaf Nodes at Minimum Level

A breadth-first walk meets the levels from the top down, so the first level on which a leaf appears is the minimum level — sum its leaves and stop.

Approach

1. If the tree is empty, return 0.
2. Start with the level holding only the root.
3. For the current level, add up the values of the nodes with no children, and collect every child into the next level.
4. If the current level had at least one leaf, return the sum; otherwise move to the next level.

Why it works

Every level above the returned one was scanned completely and held no leaf, and the returned level holds at least one, so it is exactly the minimum leaf level; every leaf on it is added because the whole level is scanned before returning.

Complexity

• Time — O(n) in the worst case, and it stops early at the first leaf level
• Space — O(w), w the largest number of nodes on one level

Pitfalls

• Return after finishing the level, not at the first leaf found — other leaves on the same level belong in the sum.
• A depth-first search must still visit the whole tree to know the minimum depth; the level walk can stop early.

Reference solution

Python

from typing import Optional

def minLeafSum(root: Optional[TreeNode]) -> int:
    level = [root] if root else []
    while level:
        total = 0
        found = False
        nxt = []
        for node in level:
            if node.left is None and node.right is None:
                total += node.val
                found = True
            if node.left:
                nxt.append(node.left)
            if node.right:
                nxt.append(node.right)
        if found:
            return total
        level = nxt
    return 0

Java

public static int minLeafSum(TreeNode root) {
    List<TreeNode> level = new ArrayList<>();
    if (root != null) level.add(root);
    while (!level.isEmpty()) {
        int total = 0;
        boolean found = false;
        List<TreeNode> next = new ArrayList<>();
        for (TreeNode node : level) {
            if (node.left == null && node.right == null) { total += node.val; found = true; }
            if (node.left != null) next.add(node.left);
            if (node.right != null) next.add(node.right);
        }
        if (found) return total;
        level = next;
    }
    return 0;
}

C++

int minLeafSum(TreeNode* root) {
    vector<TreeNode*> level;
    if (root) level.push_back(root);
    while (!level.empty()) {
        int total = 0;
        bool found = false;
        vector<TreeNode*> next;
        for (TreeNode* node : level) {
            if (!node->left && !node->right) { total += node->val; found = true; }
            if (node->left) next.push_back(node->left);
            if (node->right) next.push_back(node->right);
        }
        if (found) return total;
        level.swap(next);
    }
    return 0;
}

JavaScript

var minLeafSum = function(root) {
    var level = root === null ? [] : [root];
    while (level.length > 0) {
        var total = 0, found = false, next = [];
        for (var i = 0; i < level.length; i++) {
            var node = level[i];
            if (node.left === null && node.right === null) { total += node.val; found = true; }
            if (node.left !== null) next.push(node.left);
            if (node.right !== null) next.push(node.right);
        }
        if (found) return total;
        level = next;
    }
    return 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More breadth-first search problems

• Level of a Node in Binary Tree Easy
• Count BST Nodes That Lie in a Given Range Easy
• Nodes at Odd Levels Easy
• Kth Largest Element in BST Easy
• Ceil in BST Easy
• Nodes at Distance K from Root Easy