Skip to main content

1302 - Deepest Leaves Sum

Difficulty: Medium | Pattern: BFS Level Order / DFS | Company tags: Amazon, Facebook

Problem Statement​

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

Example 1:

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

Approach: BFS Level Order — O(n)​

Key insight: Process the tree level by level. For each level, compute the sum. The sum of the last level is the answer.

from collections import deque

def deepestLeavesSum(root) -> int:
    queue = deque([root])
    level_sum = 0
    
    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

Approach: DFS — O(n)​

def deepestLeavesSum(root) -> int:
    max_depth = [0]
    total = [0]
    
    def dfs(node, depth):
        if not node:
            return
        if depth > max_depth[0]:
            max_depth[0] = depth
            total[0] = node.val
        elif depth == max_depth[0]:
            total[0] += node.val
        dfs(node.left, depth + 1)
        dfs(node.right, depth + 1)
    
    dfs(root, 1)
    return total[0]

Algorithm Flow​

Dry Run​

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

Level 1: [1] → sum=1
Level 2: [2,3] → sum=5
Level 3: [4,5,6] → sum=15
Level 4: [7,8] → sum=15

Deepest level is 4: sum = 7+8 = 15 ✓

Edge Cases​

  • Single node → return that node's value
  • Perfectly balanced → sum of all leaf nodes

Complexity​

  • Time: O(n)
  • Space: O(w) — max queue width for BFS; O(h) for DFS

Key Terms​

TermDefinition
BFS level orderTraversing a tree level-by-level using a queue, processing all nodes at depth d before depth d+1.
DFS with depth trackingRecursing through the tree while passing the current depth, updating a running "best depth" as you go deeper.
Deepest levelThe set of nodes with the maximum depth from the root; leaves may or may not all be at this level.
Queue snapshot (len(queue))Capturing the queue's size before iterating, so exactly one level's nodes are processed per outer loop iteration.

FAQ​

  1. Can this be solved without a queue? Yes — the DFS approach uses recursion with an explicit depth counter instead of a queue, and only needs O(h) space for the recursion stack.
  2. What if the tree is empty (root = null)? Return 0. Both approaches naturally handle this: BFS starts with an empty queue and never enters the loop; DFS's base case returns immediately.
  3. Does "deepest leaves" mean only leaf nodes, or all nodes at the max depth? By the last level of BFS/DFS traversal, every node still present is necessarily a leaf (a non-leaf node at the deepest level would imply children at an even deeper level, contradicting "deepest"). So summing all nodes at the last level is equivalent to summing all deepest leaves.
  4. How would this change if we needed the deepest leaves' values, not just the sum? Instead of accumulating level_sum, collect node values into a list per level (BFS) or into a list that gets reset on max_depth[0] update (DFS).
  5. Which approach is preferred in an interview? BFS level order is usually preferred — it's iterative, avoids recursion depth limits on skewed trees, and the "last completed level is the answer" insight is easy to explain out loud.

Quick Revision​

  • Goal: sum values of all nodes at the maximum depth of a binary tree.
  • BFS: process tree level by level; after the loop ends, level_sum holds the last (deepest) level's sum.
  • DFS: track max_depth and total; reset total when a strictly deeper node is found, accumulate when depth matches max_depth.
  • Both approaches are O(n) time since every node is visited exactly once.
  • BFS space is O(w) (max width of the tree); DFS space is O(h) (tree height) for the call stack.
  • No need to store the whole tree structure — only the running sum matters.
  • Single-node tree returns that node's value.
  • Common bug: forgetting to snapshot len(queue) before the inner loop, which breaks level separation.