Deepest Leaves Sum

Medium
1943.

Deepest Leaves Sum

Deepest Leaves Sum is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google and Microsoft interviews.

Given the root of a binary tree, return the sum of the values of the leaves that lie on its deepest level.

Example 1

Input
root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output
15
Explanation
The deepest level holds 7 and 8, so the answer is 15.

Example 2

Input
root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output
19
Explanation
The deepest level holds 9, 1, 4 and 5, which add up to 19.

Example 3

Input
root = [4]
Output
4
Explanation
The root is the only (and deepest) leaf.

Constraints

  • 1 <= number of nodes <= 10^4
  • 1 <= Node.val <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var deepestLeavesSum = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Deepest Leaves Sum — Solution in Python, Java & C++

Deepest Leaves Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Deepest Leaves Sum is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google and Microsoft interviews.

Problem statement

Given the root of a binary tree, return the sum of the values of the leaves that lie on its deepest level.

Example 1

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15
Explanation: The deepest level holds 7 and 8, so the answer is 15.

Example 2

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 19
Explanation: The deepest level holds 9, 1, 4 and 5, which add up to 19.

Example 3

Input: root = [4]
Output: 4
Explanation: The root is the only (and deepest) leaf.

Constraints

  • 1 <= number of nodes <= 10^4
  • 1 <= Node.val <= 100

Hints for Deepest Leaves Sum

  1. Hint 1

    Every node on the deepest level is a leaf, so the answer is simply the sum of the last level.

  2. Hint 2

    Walk the tree level by level and remember only the sum of the level you just finished.

  3. Hint 3

    When a level produces no children, the sum you are holding is the answer.

How to solve Deepest Leaves Sum

The deepest level consists only of leaves, so a level-by-level walk that keeps the sum of the most recent level ends holding the answer.

Approach

  1. Start with the level containing only the root.
  2. For each level, add up its values and collect its children as the next level.
  3. When the next level is empty, return the sum of the current one.

Why it works

A node on the deepest level cannot have children (they would be deeper), so all its nodes are leaves, and every leaf on that level is one of its nodes. The walk ends exactly after processing that level.

Complexity

  • Time — O(n)
  • Space — O(w), w the widest level

Pitfalls

  • Summing every leaf instead of only the deepest ones.
  • A depth-first version must reset the running sum whenever it meets a deeper leaf than any seen so far.

Reference solution

Python

from typing import Optional

def deepestLeavesSum(root: Optional[TreeNode]) -> int:
    level = [root]
    while True:
        total = 0
        nxt = []
        for node in level:
            total += node.val
            if node.left:
                nxt.append(node.left)
            if node.right:
                nxt.append(node.right)
        if not nxt:
            return total
        level = nxt

Java

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

C++

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

JavaScript

var deepestLeavesSum = function(root) {
    var level = [root];
    for (;;) {
        var total = 0, next = [];
        for (var i = 0; i < level.length; i++) {
            var node = level[i];
            total += node.val;
            if (node.left !== null) next.push(node.left);
            if (node.right !== null) next.push(node.right);
        }
        if (next.length === 0) return total;
        level = next;
    }
};

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

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)