Deepest Leaves Sum

• First Pass: Find Maximum Depth
  • Define a recursive function findMaxDepth(node).
  • The base case is a null node, which has a depth of 0.
  • For a non-null node, the depth is 1 + max(findMaxDepth(node.left), findMaxDepth(node.right)).
  • Call this on the root to find the maxDepth of the entire tree.
• Second Pass: Sum at Maximum Depth
  • Define a second recursive function sumAtDepth(node, currentDepth, maxDepth).
  • Initialize a sum variable to 0.
  • Traverse the tree, passing the currentDepth.
  • If currentDepth equals maxDepth, add the node's value to the sum.
  • Recursively call for left and right children with currentDepth + 1.
• Return the final sum.

This method breaks the problem down into two simpler, sequential steps.

1. First Pass - Find Maximum Depth: We first need to know what the 'deepest' level is. We can find this by performing a standard DFS traversal. A recursive function findMaxDepth(node) can compute the height of the subtree rooted at node. The height of a null node is 0, and the height of a non-null node is 1 plus the maximum height of its left and right subtrees. By calling this on the root, we get the maximum depth of the entire tree.

2. Second Pass - Sum Deepest Leaves: Once we have the maxDepth, we traverse the tree again. This time, we use another recursive function, say sumAtDepth(node, currentDepth, maxDepth). We pass down the current depth of each node. If a node's currentDepth matches the maxDepth we found earlier, we add its value to a running total. After this second traversal is complete, the total will be our answer.

1class Solution {2    int sum = 0;3 4    public int deepestLeavesSum(TreeNode root) {5        if (root == null) {6            return 0;7        }8        int maxDepth = findMaxDepth(root);9        sumAtDepth(root, 1, maxDepth);10        return sum;11    }12 13    private int findMaxDepth(TreeNode node) {14        if (node == null) {15            return 0;16        }17        return 1 + Math.max(findMaxDepth(node.left), findMaxDepth(node.right));18    }19 20    private void sumAtDepth(TreeNode node, int currentDepth, int maxDepth) {21        if (node == null) {22            return;23        }24        if (currentDepth == maxDepth) {25            sum += node.val;26        }27        sumAtDepth(node.left, currentDepth + 1, maxDepth);28        sumAtDepth(node.right, currentDepth + 1, maxDepth);29    }30}

• Initialize two member variables: maxDepth = -1 and deepestSum = 0.
• Create a recursive DFS function dfs(node, depth).
• Base case: If node is null, return.
• If the current depth is greater than maxDepth, it means we've found a new deepest level. Update maxDepth to depth and reset deepestSum to node.val.
• Else if depth is equal to maxDepth, it means we've found another node at the current deepest level. Add node.val to deepestSum.
• Recursively call dfs for the left and right children, incrementing the depth for each call (depth + 1).
• Start the traversal with dfs(root, 0).
• Return deepestSum.

Instead of traversing the tree twice, we can gather all the necessary information in a single pass. We can perform a pre-order DFS traversal, keeping track of the current node's depth.

We use two global or member variables: maxDepth to store the maximum depth encountered so far, and deepestSum to store the sum of nodes at that maxDepth.

During the traversal, for each node at a certain depth:

• If depth > maxDepth, we have found a new, deeper level. This means any previous sum is now invalid. We update maxDepth to the current depth and reset deepestSum to the current node's value.
• If depth == maxDepth, we have found another node at the current deepest level. We simply add its value to deepestSum.
• If depth < maxDepth, we ignore the node as it's not at the deepest level.

We start the traversal from the root at depth 0. After the traversal is complete, deepestSum will hold the required result.

1class Solution {2    private int maxDepth = -1;3    private int deepestSum = 0;4 5    public int deepestLeavesSum(TreeNode root) {6        dfs(root, 0);7        return deepestSum;8    }9 10    private void dfs(TreeNode node, int depth) {11        if (node == null) {12            return;13        }14 15        if (depth > maxDepth) {16            maxDepth = depth;17            deepestSum = node.val;18        } else if (depth == maxDepth) {19            deepestSum += node.val;20        }21 22        dfs(node.left, depth + 1);23        dfs(node.right, depth + 1);24    }25}

• If the root is null, return 0.
• Initialize a Queue and add the root to it.
• Initialize a variable levelSum = 0.
• Loop while the queue is not empty:
  • Get the number of nodes in the current level: levelSize = queue.size().
  • Reset levelSum = 0.
  • Loop levelSize times:
    • Dequeue a node, currentNode.
    • Add currentNode.val to levelSum.
    • If currentNode.left is not null, enqueue it.
    • If currentNode.right is not null, enqueue it.
• After the main loop finishes, the last computed levelSum is the sum of the deepest level. Return it.

Breadth-First Search (BFS), also known as level-order traversal, is a perfect fit for this problem. The algorithm processes the tree one level at a time.

We use a Queue to facilitate the traversal. We start by adding the root to the queue. Then, we loop as long as the queue is not empty. In each iteration of the main loop, we are processing one entire level of the tree.

We first find out how many nodes are on the current level (levelSize = queue.size()). We then reset a levelSum variable to 0. We loop levelSize times, dequeuing each node of the current level, adding its value to levelSum, and enqueuing its children for the next level's processing.

Because we calculate the sum for each level and overwrite it with the sum of the next level, the value of levelSum after the main loop terminates will be the sum of the very last, i.e., the deepest, level.

1import java.util.LinkedList;2import java.util.Queue;3 4class Solution {5    public int deepestLeavesSum(TreeNode root) {6        if (root == null) {7            return 0;8        }9 10        Queue<TreeNode> queue = new LinkedList<>();11        queue.offer(root);12        int levelSum = 0;13 14        while (!queue.isEmpty()) {15            int levelSize = queue.size();16            levelSum = 0; // Reset sum for the new level17 18            for (int i = 0; i < levelSize; i++) {19                TreeNode currentNode = queue.poll();20                levelSum += currentNode.val;21 22                if (currentNode.left != null) {23                    queue.offer(currentNode.left);24                }25                if (currentNode.right != null) {26                    queue.offer(currentNode.right);27                }28            }29        }30        return levelSum;31    }32}