Problem Explanation

In this problem, you are given the root of a binary tree and are asked to find the sum of its deepest leaves. To give you an idea, let's consider the given tree:

1
2
3        1
4       / \
5      2   3
6     / \   \
7    4   5   6
8   /         \
9  7           8

The deepest leaves are 7 and 8 at level 4. Hence, the output is 7 + 8 = 15.

The algorithm should iterate through every level of the tree, track the sum at each level, and return the sum of the deepest level. We start the sum off with the root of the tree, and then iteratively we add the values of the leaves at each level; the sum is reset with the sum of the values of the leaves of each level. After exploring all the levels, what we have in the sum is the sum of the values of the deepest leaves.

To accomplish the iterations, we use Breadth First Search Strategy in a Queue. Within each level, we add all the leaves' values together to form that level's sum, simultaneously pushing their children to the queue. When we loop back to the next level, the queue should contain only nodes from that level thanks to our BFS strategy.

Python Solution

1
2python
3class Solution:
4    def deepestLeavesSum(self, root):
5        q = [root]
6        while q:
7            level = q
8            q = [child for node in q for child in (node.left, node.right) if child]
9        return sum(node.val for node in level)

Java Solution

1
2java
3class Solution {
4    public int deepestLeavesSum(TreeNode root) {
5        if (root == null)
6            return 0;
7        Queue<TreeNode> q = new LinkedList<>();
8        q.offer(root);
9        int res = 0;
10        while (!q.isEmpty()) {
11            int sz = q.size();
12            res = 0;
13            for (int i = 0; i < sz; i++) {
14                TreeNode node = q.poll();
15                res += node.val;
16                if (node.left != null)
17                    q.offer(node.left);
18                if (node.right != null)
19                    q.offer(node.right);
20            }
21        }
22        return res;
23    }
24}

Javascript Solution

1
2javascript
3var deepestLeavesSum = function(root) {
4    const queue = [root];
5    let sum = 0;
6    while(queue.length){
7        let len = queue.length;
8        sum = 0
9        
10        for(let i = 0; i < len; ++i){
11            let node = queue.shift();
12            sum += node.val;
13            if(node.left != null)
14                queue.push(node.left);
15            if(node.right != null)
16                queue.push(node.right);
17        }
18    }
19    
20    return sum;
21};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int deepestLeavesSum(TreeNode* root) {
6        queue<TreeNode* > q;
7        int sum = 0;
8        q.push(root);
9        
10        while (!q.empty()){
11            int k = q.size();
12            sum = 0;
13            while (k-- > 0){
14                TreeNode* node = q.front();
15                q.pop();
16                sum += node->val;
17                if (node->left) q.push(node->left);
18                if (node->right) q.push(node->right);
19            }
20        }
21        return sum;
22    }
23};

C# Solution

1
2csharp
3public class Solution {
4    public int DeepestLeavesSum(TreeNode root) {
5        var q = new Queue<TreeNode>();
6        q.Enqueue(root);
7        var sum = 0;
8        
9        while (q.Count != 0) {
10            var size = q.Count;
11            sum = 0;
12            
13            for (int i = 0; i < size; i++) {
14                var curr = q.Dequeue();
15                sum += curr.val;
16                
17                if (curr.left != null)
18                    q.Enqueue(curr.left);
19                if (curr.right != null)
20                    q.Enqueue(curr.right);
21            }
22        }
23        
24        return sum;
25    }
26}

Notice that we reset the sum for every level, hence we will eventually get the sum of values at the deepest level as we keep moving down the tree. The child nodes are added to the queue, so if a node has no children (indicating it is a leaf), it's value will remain in the sum, which is exactly what we want. We keep iterating until there are no more nodes in the queue. This means we've hit the deepest level of the tree and we can return the result.All the solutions provided here are using the same BFS (Breadth First Search) approach but with different languages. The essential logic is all the same. Each solution iterates through the tree level by level, calculates the sum of the current level's nodes value and stores this sum in a variable which gets reset in each level iteration. When all nodes have been processed the resultant sum would be the sum of the deepest leaves as that would be the final value present in the sum variable after the BFS traversal completes.

Time and Space Complexity

The time complexity for these solutions is O(n), where n is the number of nodes in the tree, since each node is processed exactly once.

For the space complexity, in the worst scenario the queue will be filled with all nodes at the deepest level. If d is the width of the tree at its maximum level, then space complexity is O(d). Also if the tree is perfect binary tree, then d = n/2 , so in worst-case scenario, space complexity is O(n). This is worst-case scenario when all nodes of the binary tree are stored into the queue which will only occur if all the nodes are at the deepest level.

Complexity may vary a bit based on the language and its internal handling for the data structures used in these solutions. But overall this is a fairly efficient solution for the problem. As an enhancement, we can use Dequeue instead of Queue as in Python, Java and C#, which will keep the space complexity strictly O(d), hence making the solution even more efficient.

However, when we implement solutions for such problems we have to find a balance between code readability and efficiency, because an efficient solution may not always be the most readable, and readability is a very important aspect of coding, especially in software development environments where collaboration and maintainability are key factors. So this approach strikes a good balance between those factors.