Deepest Leaves Sum

medium tree bfs dfs

Problem

Given the root of a binary tree, return the sum of the values of its deepest leaves. The deepest leaves are the nodes that sit on the lowest (farthest from the root) level of the tree.

One clean way is a level-order BFS: sweep the tree one level at a time, keeping a running sum for the level you are currently on. When the queue empties, the last sum you computed is the sum of the deepest level.

Inputlevel-order: [1, 2, 3, 4, 5, _, 6]

Output15

The tree has three levels. The deepest level holds 4, 5, and 6, and 4 + 5 + 6 = 15.

level-order ('_' for null)

from collections import deque
def deepest_leaves_sum(root):
    q = deque([root])
    total = 0
    while q:
        total = 0
        for _ in range(len(q)):
            node = q.popleft()
            total += node.val
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
    return total

function deepestLeavesSum(root) {
  let q = [root];
  let total = 0;
  while (q.length) {
    total = 0;
    const next = [];
    for (const node of q) {
      total += node.val;
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    q = next;
  }
  return total;
}

class Solution {
    public int deepestLeavesSum(TreeNode root) {
        Deque<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        int total = 0;
        while (!q.isEmpty()) {
            total = 0;
            for (int i = q.size(); i > 0; i--) {
                TreeNode node = q.poll();
                total += node.val;
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
        }
        return total;
    }
}

int deepestLeavesSum(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    int total = 0;
    while (!q.empty()) {
        total = 0;
        for (int i = q.size(); i > 0; i--) {
            TreeNode* node = q.front(); q.pop();
            total += node->val;
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return total;
}

Explanation

The "deepest leaves" are simply the nodes on the bottom level of the tree. So the whole problem reduces to: find the last level and add up its values.

A level-order BFS makes this almost free. We push the root into a queue and then process the tree one level at a time. At the start of each level we reset total to 0, drain exactly the nodes currently in the queue (that is one full level), add their values to total, and enqueue all their children for the next level.

The clever part is that we do not need to know in advance which level is the deepest. We just keep overwriting total on every level. Once the queue runs dry, the very last level we processed was the deepest, and total already holds its sum — so we return it.

Example: [1, 2, 3, 4, 5, _, 6]. Level 0 sets total = 1. Level 1 overwrites it with 2 + 3 = 5. Level 2 overwrites it with 4 + 5 + 6 = 15. The queue is now empty, so the answer is 15.

A depth-first traversal works too: track the maximum depth seen so far, and whenever you reach a deeper level, restart the sum; when you revisit that same deepest level, keep adding. BFS is usually the easier version to reason about.

Time: O(n) Space: O(w) queue width