Coding Interview PatternsDeepest Leaves Sum
MediumTree Breadth-First Search

Deepest Leaves Sum

Explanation & Solution

Practice Problem

Description

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

Examples

Example 1:

```tree

[1, 2, 3, 4, 5, null, 6, 7, null, null, null, null, 8]

`

Input:root = [1, 2, 3, 4, 5, null, 6, 7, null, null, null, null, 8]
0
1
1
2
2
3
3
4
4
5
5
null
6
6
7
7
8
null
9
null
10
null
11
null
12
8

Output: 15

Explanation: The deepest leaves are nodes with values 7 and 8. Their sum is 7 + 8 = 15.

Example 2:

```tree

[6, 7, 8, 2, 7, 1, 3, 9, null, 1, 4, null, null, null, 5]

`

Input:root = [6, 7, 8, 2, 7, 1, 3, 9, null, 1, 4, null, null, null, 5]
0
6
1
7
2
8
3
2
4
7
5
1
6
3
7
9
8
null
9
1
10
4
11
null
12
null
13
null
14
5

Output: 19

Explanation: The deepest leaves are nodes with values 9, 1, 4, and 5. Their sum is 9 + 1 + 4 + 5 = 19.

Example 3:

```tree

[1]

`

Input:root = [1]
0
1

Output: 1

Explanation: The only node is the deepest leaf.

Constraints

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

Approach

Tree Breadth-First Search pattern

1. Base Case

  • If root is null:
  • Return 0
  • Reason:
  • An empty tree has no leaves to sum

2. Initialize BFS

  • Create a queue with the root node
  • Create a variable levelSum to track the sum of the current level

3. Process Level by Level

  • While the queue is not empty:
  • Record the levelSize
  • Reset levelSum = 0 at the start of each level
  • Loop levelSize times:
  • Dequeue a node
  • Add its value to levelSum
  • Enqueue its left child if it exists
  • Enqueue its right child if it exists

4. Return the Last Level Sum

  • After the BFS completes, levelSum holds the sum of the last level processed
  • The last level is the deepest level
  • Return levelSum

Key Insight

  • BFS processes nodes level by level. By resetting the sum at each level, when the loop ends, we have the sum of the deepest level.
  • No need to track depth or find max depth first — the last level processed is always the deepest.
Time
O(n)visit each node once
Space
O(w)where w is the maximum width of the tree

Visualization

Input:
DFS Traversal[1, 2, 3, 4, 5, 6, 7, 8]
1234567
output0

Press play to start DFS traversal

CurrentIn stackComplete
15 steps

Solution Code

Previous
Add One Row to Tree
Next
Maximum Level Sum of a Binary Tree