Problem Description

The Deepest Leaves Sum problem asks you to find the sum of the values of the deepest leaves in a binary tree.

• You are given the root node of a binary tree, root.
• A leaf is a node with no children.
• The deepest leaves are all the leaf nodes that are at the deepest (greatest) level of the tree.
• Your task is to return the sum of the values of these deepest leaves.

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• 1 <= Node.val <= 100

Thought Process

The key challenge is to identify which nodes are at the deepest level of the tree, and then sum their values. If we can determine the depth of each node, we can track the nodes at the maximum depth.

A brute-force approach would be to traverse the tree, record the depth of every node, and then in a second pass, sum all nodes that are at the maximum depth. However, this is inefficient.

A better approach is to traverse the tree in such a way that we can keep track of the current depth, and whenever we reach a leaf, if it's at a new maximum depth, we reset our sum. If it's at the current maximum, we add its value to the sum.

Breadth-first search (BFS) is especially helpful here because it processes nodes level by level, so the last level we process will be the deepest leaves. Depth-first search (DFS) can also be used by keeping track of the depth as we recurse.

Solution Approach

Let's discuss both BFS and DFS approaches, but we'll implement BFS for simplicity.

• BFS (Level Order Traversal):
  1. Use a queue to traverse the tree level by level.
  2. At each level, sum the values of all nodes at that level.
  3. When you finish a level, check if there are more nodes to process; if so, reset the sum for the next level.
  4. When you finish processing the last level (the deepest), the sum at that moment is the answer.
• DFS (Recursive):
  1. Recursively traverse the tree, keeping track of the depth.
  2. When you reach a leaf, check if its depth is greater than the current known maximum; if so, reset the sum.
  3. If the depth equals the current maximum, add its value to the sum.
  4. Return the sum after traversing the whole tree.

We choose BFS for its simplicity in handling levels and summing values at each level.

Example Walkthrough

Example Input:
1
/ \
2 3
/ \ \
4 5 6
/ \
7 8

Step-by-step BFS:

1. Level 1: 1 (sum = 1)
2. Level 2: 2, 3 (sum = 2 + 3 = 5)
3. Level 3: 4, 5, 6 (sum = 4 + 5 + 6 = 15)
4. Level 4: 7, 8 (sum = 7 + 8 = 15)

The deepest leaves are 7 and 8 at level 4. So, the answer is 15.

Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

from collections import deque

class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        queue = deque([root])
        while queue:
            level_sum = 0
            for _ in range(len(queue)):
                node = queue.popleft()
                level_sum += node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return level_sum
      

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

#include <queue>

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

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

import java.util.*;

class Solution {
    public int deepestLeavesSum(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int levelSum = 0;
        while (!queue.isEmpty()) {
            levelSum = 0;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                levelSum += node.val;
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return levelSum;
    }
}
      

/**
 * Definition for a binary tree node.
 * 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) {
    let queue = [root];
    let levelSum = 0;
    while (queue.length > 0) {
        levelSum = 0;
        let size = queue.length;
        for (let i = 0; i < size; i++) {
            let node = queue.shift();
            levelSum += node.val;
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }
    return levelSum;
};
      

Time and Space Complexity

• Brute-force approach:
  • First, traverse the tree to record the depth of each node: O(N)
  • Second, traverse again to sum the deepest leaves: O(N)
  • Total time: O(N); Space: O(N) for storing depths
• Optimized BFS approach:
  • Each node is visited once: O(N)
  • The queue can at most contain all nodes at the largest level: O(W), where W is the maximum width of the tree
  • Total time: O(N); Space: O(W)

Here, N is the total number of nodes in the tree. Space is dominated by the queue in BFS, which at most holds all nodes in the largest level.

Summary

To solve the Deepest Leaves Sum problem, we use a level-order traversal (BFS) to process the tree one level at a time. By summing the node values at each level and updating the sum as we go, we ensure that the final sum corresponds to the deepest leaves. This approach is efficient, requiring only a single traversal and using space proportional to the width of the tree. The elegance of this solution lies in its simplicity and direct mapping of the algorithm to the problem's requirements.