Solution Explanation for Deepest Leaves Sum

The problem asks for the sum of values of the deepest leaves in a binary tree. Two approaches are efficient: Breadth-First Search (BFS) and Depth-First Search (DFS).

Approach 1: Breadth-First Search (BFS)

BFS is an iterative approach that explores the tree level by level. We use a queue to keep track of nodes to visit.

Algorithm:

1. Initialization: Start with a queue containing the root node.
2. Level Traversal: Iterate while the queue is not empty. In each iteration, process all nodes at the current level.
3. Sum Calculation: For each node at the current level, add its value to a running sum (ans).
4. Next Level: Add the children of the processed nodes to the queue for the next level.
5. Return: After processing all levels, the final ans represents the sum of values at the deepest level.

Time Complexity: O(N), where N is the number of nodes. Each node is visited and processed exactly once.

Space Complexity: O(W), where W is the maximum width (number of nodes) at any level of the tree. In the worst case (a complete binary tree), W can be proportional to N.

Approach 2: Depth-First Search (DFS)

DFS is a recursive approach that explores the tree branch by branch. We maintain the maximum depth seen so far and the sum of nodes at that depth.

Algorithm:

1. Initialization: max_depth keeps track of the deepest level encountered, and sum stores the sum of nodes at that level. We start with max_depth = 0 and sum = 0.
2. Recursive Traversal: The dfs function recursively visits nodes.
3. Depth Check: For each node, we compare its depth with max_depth.
   • If the depth is greater than max_depth, it's a new deepest level. Update max_depth and set sum to the node's value.
   • If the depth equals max_depth, add the node's value to sum.
4. Return: After the recursion completes, sum holds the desired result.

Time Complexity: O(N), as each node is visited once.

Space Complexity: O(H) in the worst case, where H is the height of the tree. This is due to the recursive call stack. In a skewed tree, H can be N. However, in a balanced tree, H is log₂N.

Code Examples (Python)

BFS:

from collections import deque
 
def deepestLeavesSum(root):
    q = deque([root])
    ans = 0
    while q:
        level_sum = 0
        for _ in range(len(q)):
            node = q.popleft()
            level_sum += node.val
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        ans = level_sum  # Update ans with the sum of the current level
    return ans
 

DFS:

def deepestLeavesSum(root):
    max_depth = 0
    sum_at_depth = 0
 
    def dfs(node, depth):
        nonlocal max_depth, sum_at_depth
        if not node:
            return
        if depth > max_depth:
            max_depth = depth
            sum_at_depth = node.val
        elif depth == max_depth:
            sum_at_depth += node.val
        dfs(node.left, depth + 1)
        dfs(node.right, depth + 1)
 
    dfs(root, 0)
    return sum_at_depth
 

Note: Both BFS and DFS solutions provide optimal time complexity. The choice between them often depends on factors like memory constraints (BFS might be preferred for very wide trees) and coding style preference. The provided code examples are in Python, but similar implementations are possible in other languages (Java, C++, JavaScript, etc.). Remember to adapt the code based on your specific tree node structure.