Problem

Given the root of a binary tree, return the sum of values of its deepest leaves.

Examples

Example 1:

graph TD
	1 --- 2 & 3
	2 --- 4 & 5
	4 --- 7
	4 ~~~ N1:::hidden
	3 ~~~ N2:::hidden
	3 --- 6
	6 ~~~ N3:::hidden
	6 --- 8

classDef hidden display:none
  
1
2
3
4

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

Example 2:

1
2
3
4

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

Solution

Method 1 - Using Level Order Traversal

The problem requires calculating the sum of values at the deepest level of leaves in a binary tree. To achieve this, we use Breadth-First Search (BFS) or Level Order Traversal. The idea is simple and efficient:

  1. Traverse the tree level by level.
  2. For each level, calculate the sum of node values.
  3. Finally, the sum of the last level (deepest level) will be the required result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public int deepestLeavesSum(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int ans = 0;
        
        while (!q.isEmpty()) {
            ans = 0; // Reset the sum for the current level
            int size = q.size();
            
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                ans += node.val; // Add current node value to the sum
                
                if (node.left != null) {
                    q.add(node.left); // Add left child if exists
                }
                if (node.right != null) {
                    q.add(node.right); // Add right child if exists
                }
            }
        }
        
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
        q: deque[TreeNode] = deque([root])
        ans: int = 0
        
        while q:
            ans = 0  # Reset the sum for the current level
            for _ in range(len(q)):  # Iterate over nodes of the current level
                node = q.popleft()
                ans += node.val  # Add current node value to the sum
                
                if node.left:
                    q.append(node.left)  # Add left child if exists
                if node.right:
                    q.append(node.right)  # Add right child if exists
        
        return ans

Complexity

  • ⏰ Time complexity: - O(n). We touch each node exactly once during tree traversal.
  • 🧺 Space complexity: O(n). In the worst case, the queue can store all the nodes of the last level, and in a binary tree, the last level can have up to n/2 nodes in a full tree.