Problem Breakdown
We are tasked with finding the sum of values belonging specifically to the “deepest leaves” in a binary tree. A leaf is defined as a node without children (left and right pointers are null). The deepest level refers to the maximum depth from the root where nodes exist.
Inputs:
root: Pointer to the head of a Binary Tree (TreeNode).
Outputs:
- An integer representing the sum of values at the maximum depth.
Implicit Constraints & Edge Cases:
- Empty Input: While constraints state node count , robust code handles
Noneroot gracefully (returning 0). - Single Node Tree: The single node is both a leaf and the deepest level; sum should be its value.
- Skewed Trees: A tree that looks like a linked list has depth but only one path of leaves at the bottom. Logic must handle non-balanced structures correctly without relying on height balancing assumptions.
- Values: Node values are positive (), preventing negative sum issues, though logic holds regardless.
Intuition
A brute-force approach might involve calculating the tree’s maximum depth first (via DFS or BFS) and then traversing again to collect nodes at that specific level. This requires two passes over the data ( time but higher constant factor). Alternatively, one could use a hash map mapping depth -> sum, which is space overhead for storage if not careful.
Key Insight: Breadth-First Search (Level Order Traversal) naturally processes nodes layer-by-layer from top to bottom. If we maintain the running sum of values at each level, and update our final answer variable with every new non-empty level processed, the last value stored in that accumulator will correspond exactly to the deepest leaves. This happens because BFS exhausts all levels before moving deeper; once a level has no children (leaves), it is added to the queue but produces nothing for subsequent iterations.
Why Brute Force Fails: A naive DFS approach tracking depth and resetting sums when encountering a new max-depth requires careful state management to avoid double-counting or missing nodes if not implemented precisely with global variables per level. BFS provides cleaner separation of levels using a queue size counter, making the logic more robust against implementation errors regarding tree structure irregularities.
Approach
- Base Case Check: If
rootis null, return 0 immediately (though constraints imply valid trees). - Initialization: Use a deque for efficient queue operations. Initialize with the root node. Set up an accumulator variable (
ans) to store the sum of the current deepest level found so far. - Level-by-Level Traversal:
- While the queue is not empty, process all nodes currently in the queue (representing one depth).
- For each iteration of a specific depth: pop node value and add it to
current_level_sum. Add valid children to the end of the queue for the next level.
- Update Answer: After processing every complete level, update the global answer (
ans) withcurrent_level_sum. This ensures that if we find deeper levels later in the traversal, they overwrite previous sums automatically. - Termination: The loop terminates when no children exist for any node (queue becomes empty). The last value stored in
ansis our result.
Complexity Analysis
- Time Complexity: where is the number of nodes. We visit every node exactly once during the BFS traversal to check its existence and add it to children lists or accumulate values.
- Space Complexity: , where is the maximum width (number of nodes at any level) of the tree. In a balanced binary tree, this approaches . The queue stores all active nodes for the current depth during traversal.
Solution
from collections import deque
from typing import Optional
# Definition for a Node in a Binary Tree
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def deepestLeavesSum(root: Optional['TreeNode']) -> int:
# Handle edge case where tree is empty (though constraints say N >= 1)
if not root:
return 0
queue = deque([root])
# This variable will hold the sum of values for each level processed.
# We overwrite it in every iteration, so by the end, it holds
# the sum of the deepest leaves (the last non-empty level).
ans = 0
while queue:
current_level_sum = 0
# Process all nodes at the current depth
for _ in range(len(queue)):
node = queue.popleft()
# Accumulate value of leaf or internal node (all contribute to deepest level sum)
current_level_sum += node.val
# Add children to queue if they exist; these will be processed
# as the next deeper level.
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# Update answer with sum of current deepest leaves found so far
ans = current_level_sum
return ans
# Example usage logic (not part of function signature for LeetCode submission):
# root = TreeNode(1,
# left=TreeNode(2), right=TreeNode(3)
# ) # ... etc.
Edge Cases Handled
- Single Node Tree: The loop runs once;
current_level_sumcaptures the single node’s value; queue becomes empty after children check (none); returns correct sum. - Skewed/Unbalanced Trees: BFS handles any topology equally well as it relies on level counts rather than tree height assumptions, ensuring performance regardless of shape.
- Null Root Check: Explicitly handled at the start to prevent errors if input violates constraints (defensive programming).