Knowledge Guide
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

Image
Image
Image
Image
Image
Image

Try it yourself

Try solving this question here:

✅ 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]
Image
Image

  • 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]
Image
Image

  • 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]
Image
Image
  • 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

  1. Check for Empty Tree:

    • If the root node is null, return 0 as the tree is empty, and there are no leaves to sum.

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

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

  4. 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]

  1. Initialization:

    • The tree is not empty, so we proceed.
    • Queue = [1], levelSum = 0.

  2. 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].

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

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

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

🤖 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 ImageFurthest Building You Can Reach →