Find Largest subtree sum in a tree

The problem, simply

You get a binary tree of numbers, some of them negative. A subtree is a node together with everything below it. Its sum is all of those numbers added up.

Find the largest subtree sum in the whole tree. The subtree can start at any node, including a single leaf or the root.

A story to remember it

Picture it

Examples

Way 1: the simple way

For every node, add up its whole subtree from scratch, and keep the biggest sum.

1. Visit every node.
2. At each node, walk its whole subtree to get its sum.
3. Keep the largest sum seen.

class Solution {
    private int best;

    public int largestSubtreeSum(TreeNode root) {
        if (root == null) return 0;
        best = Integer.MIN_VALUE;
        visit(root);
        return best;
    }

    private void visit(TreeNode n) {
        if (n == null) return;
        best = Math.max(best, sum(n));   // add up this whole subtree again
        visit(n.left);
        visit(n.right);
    }

    private int sum(TreeNode n) {
        if (n == null) return 0;
        return n.val + sum(n.left) + sum(n.right);
    }
}

How long it takes: every node adds up everything below it again. In a stick shaped tree that is about n * n / 2 steps, O(n^2). Extra room: the waiting helpers, O(h).

Way 2: the clever way

Add up each subtree once, from the bottom up. A helper returns its subtree sum to its parent, so the parent never walks down again. Each helper also compares its sum with the best so far.

1. An empty spot returns 0.
2. Get the left sum l and the right sum r.
3. This subtree's sum is node + l + r. Update the best.
4. Return the sum to the parent.

class Solution {
    private int best;

    public int largestSubtreeSum(TreeNode root) {
        if (root == null) return 0;
        best = Integer.MIN_VALUE;     // not 0: all sums may be negative
        sum(root);
        return best;
    }

    // returns the sum of this subtree and updates best
    private int sum(TreeNode n) {
        if (n == null) return 0;
        int s = n.val + sum(n.left) + sum(n.right);
        best = Math.max(best, s);
        return s;
    }
}

How long it takes: each node is visited once, O(n). Extra room: the waiting helpers, O(h).

Watch out for

• Empty subtrees are not branches. An empty side adds 0 to its parent, but 0 is not a candidate answer by itself.
• Mixing this up with maximum path sum. A subtree takes everything below a node. A path picks one route and can skip parts. Here you cannot drop a bad child.
• Big totals can overflow int. Use long for large values.

What interviewers ask next

• Return the root of the best subtree, not just the sum? Save the node whenever best changes.
• Most frequent subtree sum? Count each sum in a map during the same walk (LeetCode 508).
• Maximum path sum instead? Return the best downward path (dropping a negative side), and update the answer with node + left + right (LeetCode 124).
• Largest sum of a binary search subtree? Return extra facts per node (is it a search tree, its min, max and sum) and only count valid ones (LeetCode 1373).

Remember this

Grown-up words: the branch is a subtree, its worth is the subtree sum, asking children first is post order traversal, and the best so far is a running maximum.