Deepest Leaves Sum

solution.md

Question

Given a binary tree, return the sum of values of its deepest leaves.

Solutions

Recursive Depth First Search

Intuition

Find the largest depth first, then sum up each node at the largest depth

Algorithm

We can solve this using a recursive DFS approach where we first find the maximum depth of the tree. Then, sum up each node at that maximum depth. This can also be done iteratively using a Stack data structure instead of a recursive approach.

class Solution {
    int maxDepth;
    HashMap<Integer, List<TreeNode>> map;
    public int deepestLeavesSum(TreeNode root) {
        if (root == null) return 0;
        // We'll keep track of the maximum depth of the tree
        maxDepth = 0;
        // and a map of nodes at each depth
        map = new HashMap<>();
        dfs(root, 0);
        
        // return the sum of the nodes at the max depth
        List<TreeNode> list = map.get(maxDepth);
        int sum = 0;
        for (TreeNode n : list) sum += n.val;
        return sum;
    }
    
    public void dfs(TreeNode node, int depth) {
        if (node == null) return;
        // add the current node to the map at the given depth
        List<TreeNode> list = map.getOrDefault(depth, new ArrayList<>());
        list.add(node);
        map.put(depth, list);
        maxDepth = Math.max(maxDepth, depth);
        
        // continue for each child
        dfs(node.left, depth + 1);
        dfs(node.right, depth + 1);
    }
}

Complexity

Runtime: O(N) where N = number of nodes in the tree

Space: O(N) since we store each node within a HashMap and use recursion to perform DFS

Breadth First Search

Instead of using extra memory to store each node by its depth, we can iterate in a way that we reach each node at a given depthat the same time. This is an inherent quality of a BFS since you can think of the traversal as a depth by depth traversal of the tree.

public int deepestLeavesSum(TreeNode root) {
    if (root != null) q.add(root);
    Queue<TreeNode> q = new LinkedList<>();
    // We'll sum up the nodes at each depth and the last sum will be at the max depth
    int sum = 0;
    // represents the number of TreeNodes at the current depth
    int curr = 1;
    // represents the number of TreeNodes at the next depth
    int next = 0;
    while (!q.isEmpty()) {
        TreeNode n = q.poll();
        if (n.left != null) {
            q.add(n.left);
            next++;
        }
        if (n.right != null) {
            q.add(n.right);
            next++;
        }
        curr--;
        sum += n.val;
        
        // If there are no more nodes in the current depth,
        // then we have completed a depth and can reset our counters
        if (curr == 0) {
            curr = next;
            next = 0;
            if (!q.isEmpty()) {
                sum = 0;
            }
        }
    }
    return count;
}

Complexity

Runtime: O(N) since we iterate through each depth of the tree

Space: O(max(width)) the peak capacity of the queue is determined by the level with the largest width