# Deepest Leaves Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/deepest-leaves-sum)
Canonical: https://scaleengineer.com/dsa/problems/deepest-leaves-sum
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Myntra](https://scaleengineer.com/companies/myntra)
---
## Problem
Given the `root` of a binary tree, return _the sum of values of its deepest leaves_. 

**Example 1:**

![](https://assets.glich.co/dsa/deepest-leaves-sum/image0.png) 

**Input:** root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
**Output:** 15

**Example 2:**

**Input:** root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
**Output:** 19

**Constraints:**

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

# Approaches
## Two-Pass Depth-First Search (DFS)
This approach involves two separate traversals of the tree. The first traversal is to determine the maximum depth of the tree. The second traversal then sums up the values of all nodes that are at this maximum depth.
**Time:** O(N), where N is the number of nodes. The first pass to find the depth takes O(N) and the second pass to sum the values also takes O(N). O(N) + O(N) = O(N). · **Space:** O(H), where H is the height of the tree, for the recursion stack. In the worst-case scenario of a skewed tree, H can be equal to N, making the space complexity O(N).
**Pros:** Conceptually straightforward as it breaks the problem into two distinct, simpler subproblems.
**Cons:** Inefficient as it requires traversing the entire tree twice.
### Explanation
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.

```java
class Solution {
    int sum = 0;

    public int deepestLeavesSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int maxDepth = findMaxDepth(root);
        sumAtDepth(root, 1, maxDepth);
        return sum;
    }

    private int findMaxDepth(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(findMaxDepth(node.left), findMaxDepth(node.right));
    }

    private void sumAtDepth(TreeNode node, int currentDepth, int maxDepth) {
        if (node == null) {
            return;
        }
        if (currentDepth == maxDepth) {
            sum += node.val;
        }
        sumAtDepth(node.left, currentDepth + 1, maxDepth);
        sumAtDepth(node.right, currentDepth + 1, maxDepth);
    }
}
```
### Algorithm
- **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.

## One-Pass Depth-First Search (DFS)
This approach optimizes the two-pass method by combining the two steps into a single traversal. We use a single DFS traversal to find the deepest leaves and sum their values simultaneously. We keep track of the maximum depth seen so far and the sum at that depth.
**Time:** O(N), where N is the number of nodes, as each node is visited exactly once. · **Space:** O(H), where H is the height of the tree, for the recursion stack. In the worst-case scenario of a skewed tree, H can be equal to N, making the space complexity O(N).
**Pros:** Efficient as it traverses the tree only once.; Combines finding the max depth and summing into a single, elegant recursive function.
**Cons:** Relies on member variables to maintain state across recursive calls, which can sometimes be less clean than passing state as parameters.; Recursive nature might lead to a stack overflow for extremely deep trees.
### Explanation
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.

```java
class Solution {
    private int maxDepth = -1;
    private int deepestSum = 0;

    public int deepestLeavesSum(TreeNode root) {
        dfs(root, 0);
        return deepestSum;
    }

    private void dfs(TreeNode node, int depth) {
        if (node == null) {
            return;
        }

        if (depth > maxDepth) {
            maxDepth = depth;
            deepestSum = node.val;
        } else if (depth == maxDepth) {
            deepestSum += node.val;
        }

        dfs(node.left, depth + 1);
        dfs(node.right, depth + 1);
    }
}
```
### Algorithm
- 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`.

## Breadth-First Search (BFS) / Level Order Traversal
This is an iterative approach that is very natural for level-based tree problems. We traverse the tree level by level, from top to bottom, using Breadth-First Search (BFS). For each level, we calculate the sum of its nodes' values. The sum of the very last level we process will be our answer.
**Time:** O(N), where N is the number of nodes. Each node is enqueued and dequeued exactly once. · **Space:** O(W), where W is the maximum width of the tree. This is for the space used by the queue. In the worst case of a complete binary tree, the last level can contain roughly N/2 nodes, making the space complexity O(N).
**Pros:** Iterative approach, which avoids the risk of stack overflow on very deep trees.; Very intuitive for level-based problems, as it processes the tree one level at a time.; Efficient single-pass traversal.
**Cons:** The space complexity can be high for wide trees. In the worst case (a complete binary tree), the queue can hold up to N/2 nodes.
### Explanation
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.

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

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

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

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            levelSum = 0; // Reset sum for the new level

            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                levelSum += currentNode.val;

                if (currentNode.left != null) {
                    queue.offer(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.offer(currentNode.right);
                }
            }
        }
        return levelSum;
    }
}
```
### Algorithm
- 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.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public 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; * } * } */ class Solution { public int deepestLeavesSum ( TreeNode root ) { Deque < TreeNode > q = new ArrayDeque <>(); q . offer ( root ); int ans = 0 ; while (! q . isEmpty ()) { ans = 0 ; for ( int n = q . size (); n > 0 ; -- n ) { root = q . pollFirst (); ans += root . val ; if ( root . left != null ) { q . offer ( root . left ); } if ( root . right != null ) { q . offer ( root . right ); } } } return ans ; } }
```

### CPP

```cpp
/** * 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) {} * }; */ class Solution { public: int deepestLeavesSum ( TreeNode * root ) { int ans = 0 ; queue < TreeNode *> q { { root } }; while ( ! q . empty ()) { ans = 0 ; for ( int n = q . size (); n ; -- n ) { root = q . front (); q . pop (); ans += root -> val ; if ( root -> left ) q . push ( root -> left ); if ( root -> right ) q . push ( root -> right ); } } return ans ; } };
```

### Python

```python
# 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 class Solution : def deepestLeavesSum ( self , root : Optional [ TreeNode ]) -> int : q = deque ([ root ]) while q : ans = 0 for _ in range ( len ( q )): root = q . popleft () ans += root . val if root . left : q . append ( root . left ) if root . right : q . append ( root . right ) return ans
```