Home › DSA › Company Practice

medium Deepest Leaves Sum

Problem Statement

Given a root node of the binary tree, return the sum of all values located at the deepest leaves of a binary tree.

Examples

Example 1:
- Input: root = [1,2,3,4,5,null,7]

Expected Output: 16
Justification: The deepest level contains the nodes with values 4, 5, and 7, and their sum is 16.
Example 2:
- Input: root = [6,2,8,null,null,7,9,null,null,null,10]

Expected Output: 10
Justification: The deepest level contains only one node with the value 10, thus the sum is 10.
Example 3:
- Input: root = [1,null,2,null,3,null,4]

Expected Output: 4
Justification: The binary tree's deepest level has a single node with the value 4. Since it's the only node at that level, the sum is 4.

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Deepest Leaves Sum medium

0. Pattern family

Family: BFS last level sum / DFS depth track

1. Why / judgment (K3)

Sum nodes at maximum depth. BFS: sum last level when queue drains. DFS: track maxDepth and accum.

2. Worked complexity / derivation (K11)

O(n)/O(w).

3. Pattern + recognition + when-NOT (K12)

Name: DEEPEST LEVEL AGGREGATE

Recognition: sum/count nodes at max depth.

When-NOT: Sum all leaves any depth; diameter.

4. Edge hand-run (K13)

Perfect tree last level; skewed one leaf; root only.

5. Interviewer follow-ups & drills

Q1. BFS natural?
Model answer: Level-order last batch is deepest.

Q2. DFS need two passes?
Model answer: One pass with global maxDepth reset accum when deeper found.

Q3. Leaf vs deepest?
Model answer: Non-leaf cannot be deepest if children exist — deepest nodes are leaves.

✅ Solution Deepest Leaves Sum

Problem Statement

Given a root node of the binary tree, return the sum of all values located at the deepest leaves of a binary tree.

Examples

Example 1:
- Input: root = [1,2,3,4,5,null,7]

Expected Output: 16
Justification: The deepest level contains the nodes with values 4, 5, and 7, and their sum is 16.
Example 2:
- Input: root = [6,2,8,null,null,7,9,null,null,null,10]

Expected Output: 10
Justification: The deepest level contains only one node with the value 10, thus the sum is 10.
Example 3:
- Input: root = [1,null,2,null,3,null,4]

Expected Output: 4
Justification: The binary tree's deepest level has a single node with the value 4. Since it's the only node at that level, the sum is 4.

Solution

To solve this problem, the approach involves a breadth-first search (BFS) traversal of the binary tree. This method is chosen because BFS explores the tree level by level, starting from the root, making it efficient to identify the deepest leaves. By utilizing a queue to keep track of nodes and their levels, we can process each level of the tree sequentially. Once we reach the last level, we calculate the sum of all nodes at that level.

This approach is effective because it ensures that we visit all nodes in the tree while maintaining a clear distinction between different levels. By doing so, we can easily identify when we've reached the deepest level and then sum up the values of the nodes at this level. It is also efficient, as each node is visited exactly once, and no unnecessary computations are done.

Step-by-Step Algorithm

Check for Empty Tree:
- If the root node is null, return 0 as the tree is empty, and there are no leaves to sum.
Initialize Queue and Variables:
- Initialize a queue to hold the nodes of the tree along with their level. Start by enqueuing the root node.
- Initialize levelSum to 0. This variable will hold the sum of the values of the nodes at the current (deepest) level.
Breadth-First Search (BFS) Loop:
- While the queue is not empty, perform the following steps to process each level of the tree:
  - Note the size of the queue at the start of the loop iteration. This size represents the number of nodes at the current level, as all nodes in the queue are from the same level.
  - Reset levelSum to 0 at the start of processing a new level.
  - Loop through the nodes at the current level (using the noted size of the queue to ensure only nodes of the current level are processed):
    - Dequeue a node from the queue.
    - Add the value of the dequeued node to levelSum.
    - If the dequeued node has a left child, enqueue this child.
    - If the dequeued node has a right child, enqueue this child.
Return Sum of Deepest Leaves:
- After the loop ends (i.e., the queue is empty, and all levels have been processed), levelSum contains the sum of the values of the nodes at the deepest level of the tree.
- Return levelSum.

Algorithm Walkthrough

Let's consider the Input: root = [1,2,3,4,5,null,7]

Initialization:
- The tree is not empty, so we proceed.
- Queue = [1], levelSum = 0.
First Level Processing (Root Level):
- Queue size at start = 1 (contains root node 1).
- levelSum reset to 0.
- Dequeue 1: Queue = [], levelSum = 1 (value of node 1).
- Enqueue children of 1: Queue = [2, 3].
Second Level Processing:
- Queue size at start = 2 (contains nodes 2 and 3).
- levelSum reset to 0.
- Dequeue 2: Queue = [3], levelSum = 2 (value of node 2).
- Enqueue children of 2: Queue = [3, 4, 5].
- Dequeue 3: Queue = [4, 5], levelSum = 5 (2 + value of node 3).
- Enqueue right child of 3 (node 7): Queue = [4, 5, 7].
Third Level Processing:
- Queue size at start = 3 (contains nodes 4, 5, and 7).
- levelSum reset to 0.
- Dequeue 4: Queue = [5, 7], levelSum = 4.
- No children to enqueue.
- Dequeue 5: Queue = [7], levelSum = 9 (4 + value of node 5).
- No children to enqueue.
- Dequeue 7: Queue = [], levelSum = 16 (9 + value of node 7).
- No children to enqueue.
Return Sum:
- With the queue empty and all levels processed, the loop ends.
- levelSum is 16, which is the sum of the values of the nodes at the deepest level.
- Return 16.

Code

java

import java.util.LinkedList;
import java.util.Queue;

// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
// }

public class Solution {

  public int deepestLeavesSum(TreeNode root) {
    if (root == null) return 0;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    int levelSum = 0; // Sum of nodes at the current level

    while (!queue.isEmpty()) {
      int levelSize = queue.size(); // Number of nodes at the current level
      levelSum = 0; // Reset sum for the current level

      for (int i = 0; i < levelSize; ++i) {
        TreeNode currentNode = queue.poll();
        levelSum += currentNode.val; // Add the value of the current node to the sum

        // Enqueue children of the current node
        if (currentNode.left != null) queue.offer(currentNode.left);
        if (currentNode.right != null) queue.offer(currentNode.right);
      }
    }

    // After the loop, levelSum contains the sum of the deepest leaves
    return levelSum;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    TreeNode root1 = new TreeNode(1);
    root1.left = new TreeNode(2);
    root1.right = new TreeNode(3);
    root1.left.left = new TreeNode(4);
    root1.left.right = new TreeNode(5);
    root1.right.right = new TreeNode(7);
    System.out.println("Example 1: " + solution.deepestLeavesSum(root1)); // Expected Output: 16

    // Example 2
    TreeNode root2 = new TreeNode(6);
    root2.left = new TreeNode(2);
    root2.right = new TreeNode(8);
    root2.right.left = new TreeNode(7);
    root2.right.right = new TreeNode(9);
    root2.right.right.right = new TreeNode(10);
    System.out.println("Example 2: " + solution.deepestLeavesSum(root2)); // Expected Output: 10

    // Example 3
    TreeNode root3 = new TreeNode(1);
    root3.right = new TreeNode(2);
    root3.right.right = new TreeNode(3);
    root3.right.right.right = new TreeNode(4);
    System.out.println("Example 3: " + solution.deepestLeavesSum(root3)); // Expected Output: 4
  }
}

Complexity Analysis

Time Complexity

The time complexity is , where (N) is the number of nodes in the binary tree. This is because each node in the tree is visited exactly once during the BFS traversal.

Space Complexity

The space complexity is , where (W) is the maximum width of the tree. This occurs at the level with the most nodes, which dictates the maximum number of elements that can be stored in the queue at any time. In the worst case, a binary tree could be a complete binary tree, where the last level has nodes, making the space complexity in such scenarios.

🎯 STRICT STANDOUT — Solution Deepest Leaves Sum

0. Pattern family

Family: Tree BFS / last-level aggregate

1. Why / judgment (K3)

Deepest-leaves sum is a level-order problem: the deepest leaves are exactly the nodes on the last non-empty BFS level. Track depth or simply overwrite sum each level; final level’s sum is the answer. DFS also works if you track max depth then sum nodes at that depth — two passes or one pass with max bookkeeping.

2. Worked complexity / derivation (K11)

BFS: visit each node once → Θ(n) time.
Queue holds a level; worst width Θ(n) (complete tree mid-levels) → space Θ(n).
DFS: Θ(n) time, O(h) stack; if two-pass, still Θ(n).
Cannot do better than Θ(n) — must look at every node in worst case.

3. Pattern + recognition + when-NOT (K12)

Name: LAST BFS LEVEL SUM

Recognition: aggregate only deepest leaves; tree not BST-required; level or max-depth marker.

When-NOT: Not “sum all leaves” (shallow leaves excluded). Not path-sum to root. BST order irrelevant — do not binary-search.

4. Edge hand-run (K13)

Single node [7] → 7.
Perfect tree leaves at same depth → sum of all leaves.
Skewed chain → only the single deepest node.
Empty root: constraints usually n≥1; defend null → 0.

5. Interviewer follow-ups & drills

Q1. BFS vs DFS preference?
Model answer: BFS makes “last level” obvious; DFS needs maxDepth state.

Q2. Why not diameter?
Model answer: Diameter is longest path; here we sum values on max-depth layer.

Q3. Rightmost deepest?
Model answer: Different problem (cousin/right-side view); still BFS, pick last node per level.

🧩 Pattern · Trees

Recognize it: Hierarchical data → recurse on children; BFS (queue) for level-order, DFS (recursion) for paths.

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Deepest Leaves Sum? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Deepest Leaves Sum** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Deepest Leaves Sum** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Deepest Leaves Sum**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Deepest Leaves Sum**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Rotate Image Furthest Building You Can Reach →