Deepest Leaves Sum

Deepest Leaves Sum

What is this problem about?

The Deepest Leaves Sum interview question tasks you with finding the sum of the values of the nodes that are at the maximum depth of a binary tree. This Deepest Leaves Sum coding problem involves two steps: identifying the maximum depth and then summing the nodes at that depth.

Why is this asked in interviews?

Companies like Google and TikTok ask this to test your tree traversal skills. It evaluates if you can use Breadth-First Search (BFS) or Depth-First Search (DFS) to track level-specific information. It’s a great problem for discussing the trade-offs between BFS (which naturally processes level by level) and DFS (which requires tracking the maximum depth found so far).

Algorithmic pattern used

This follows the Breadth-First Search, Depth-First Search, Binary Tree interview pattern.

1. BFS approach: Use a queue to perform a level-order traversal. For each level, calculate the sum of its nodes. Since the last level processed will be the deepest, its sum is the answer.
2. DFS approach: Traverse the tree while passing the current depth. Maintain two global variables: max_depth and sum. If the current depth > max_depth, update max_depth and reset sum to the current node's value. If depth == max_depth, add the node's value to the sum.

Example explanation

Tree:

    1
   / 
  2   3
 / \   
4   5   6
       /
      7

• Level 0: [1]. Sum = 1.
• Level 1: [2, 3]. Sum = 5.
• Level 2: [4, 5, 6]. Sum = 15.
• Level 3: [7]. Sum = 7. The deepest level is 3. The sum is 7.

Common mistakes candidates make

• Multiple passes: Finding the max depth in one pass and then summing in a second pass. While correct (O(N)), it's more elegant to do it in one.
• Incorrect max depth check: In DFS, forgetting to reset the sum when a new deeper level is discovered.
• Level order tracking: In BFS, forgetting to clear the sum at the start of every new level.

Interview preparation tip

For problems involving "the last level" or "all nodes at depth X," BFS is almost always more intuitive. It avoids the need to maintain global state or reset variables as you would in DFS.