Deepest Leaves Sum

Problem Statement

In this problem, you are given the root of a binary tree and your task is to compute the sum of the values of its leaves at the deepest level. A binary tree is a type of data structure in which each node has at most two children, referred to as the left child and the right child. The deepest leaves of a binary tree are those leaves that are furthest from the root, i.e., they have the maximum depth within the tree. The value at each node can range from 1 to 100, and the structure of the binary tree may vary significantly, with a node count that can scale up to 10,000. This requires a solution that can handle large inputs efficiently while navigating to the deepest part of the tree to perform the summation.

Examples

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

Constraints

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

Approach and Intuition

Understanding and solving this problem involves a few clear steps based on the properties of trees and how we can perform traversal operations. Given the constraints and requirements, a breadth-first search (BFS) approach is suitable because it explores the nodes level by level, ensuring we only consider the deepest leaves when we complete the traversal.

1. Initialize a Queue for BFS: Start the BFS from the root node by adding it to a queue. BFS is suitable here as it will help visit each level completely before moving onto the next.

2. Track Current Level Sum: We'll keep a variable to sum the values of nodes at the current level. This variable will be reset and recalculated for each level we visit.

3. Traverse Each Level: While there are nodes in the queue:

   • Start by noting the number of nodes at the current level (queue's size at the beginning of the level).
   • Reset the current level sum to zero.
   • For each node in the current level:
     • Dequeue the node, add its value to the current level sum.
     • If the node has children, enqueue them to be processed in the next level.

4. Last Level's Sum: By the time we exit the loop, the last computed 'current level sum' corresponds to the sum of the values of the deepest leaves, as the BFS does not proceed beyond the deepest level.

This approach ensures a linear time complexity relative to the number of nodes, as each node is processed exactly once. Using BFS allows us to seamlessly handle the calculation for any form of binary tree, ensuring that we only compute the sum for the deepest leaves efficiently and accurately.

Solutions

class Solution {
  public int deepestLeavesSum(TreeNode root) {
    ArrayDeque<TreeNode>  nextQueue = new ArrayDeque(),
                          currentQueue = new ArrayDeque();
    nextQueue.offer(root);

    while (!nextQueue.isEmpty()) {
      currentQueue = nextQueue.clone();
      nextQueue.clear();

      for (TreeNode node: currentQueue) {
        if (node.left != null) {
          nextQueue.offer(node.left);
        }
        if (node.right != null) {
          nextQueue.offer(node.right);
        }
      }
    }
    int totalDeepestLeafSum = 0;
    for (TreeNode node: currentQueue) {
      totalDeepestLeafSum += node.val;
    }
    return totalDeepestLeafSum;
  }
}

class Solution:
    def deepestSum(self, root: TreeNode) -> int:
        forthcoming_level = deque([root,])
        
        while forthcoming_level:
            current_level = forthcoming_level
            forthcoming_level = deque()
            
            for node in current_level:
                if node.left:
                    forthcoming_level.append(node.left)
                if node.right:
                    forthcoming_level.append(node.right)
        
        return sum(node.val for node in current_level)