Sum of Nodes on the Longest path from root to leaf node

The problem, simply

Every node of a binary tree holds a number. A root to leaf path starts at the root and goes down until it reaches a node with no children (a leaf).

Find the longest such path, the one with the most nodes, and return the sum of its numbers. If two or more paths are equally long, return the biggest sum among them.

A story to remember it

Picture it

Examples

Way 1: the simple way

Write down every root to leaf path as its own list. Then go through the lists: find the longest, and among the longest, the biggest sum.

1. Walk down with a list of the nodes so far. At each leaf, save a copy of the list.
2. For each saved list, compute its length and sum.
3. Keep the best by "longer, or same length and bigger sum".

import java.util.*;

class Solution {
    public int sumOfLongRootToLeafPath(TreeNode root) {
        if (root == null) return 0;
        List<List<Integer>> paths = new ArrayList<>();
        collect(root, new ArrayList<>(), paths);
        int bestLen = 0, bestSum = Integer.MIN_VALUE;
        for (List<Integer> p : paths) {
            int sum = 0;
            for (int v : p) sum += v;
            if (p.size() > bestLen || (p.size() == bestLen && sum > bestSum)) {
                bestLen = p.size();
                bestSum = sum;
            }
        }
        return bestSum;
    }

    private void collect(TreeNode node, List<Integer> path, List<List<Integer>> paths) {
        if (node == null) return;
        path.add(node.val);
        if (node.left == null && node.right == null) paths.add(new ArrayList<>(path));  // a leaf: save a copy
        collect(node.left, path, paths);
        collect(node.right, path, paths);
        path.remove(path.size() - 1);
    }
}

How long it takes: there can be up to about n / 2 leaves, and each saved copy is up to h long, so O(n * h). Extra room: all those copies, also O(n * h).

Way 2: the clever way

Carry only two numbers down: the length so far and the sum so far. At each leaf, update a best length and best sum. Nothing is copied.

1. Start at the root with length 0 and sum 0.
2. At each node, add 1 to the length and the value to the sum.
3. At a leaf: if the length is bigger than the best length, take this length and sum. If the length is equal and the sum is bigger, take this sum.
4. Otherwise go into both children with the new numbers.

class Solution {
    private int bestLen, bestSum;

    public int sumOfLongRootToLeafPath(TreeNode root) {
        if (root == null) return 0;
        bestLen = 0;
        bestSum = Integer.MIN_VALUE;
        walk(root, 0, 0);
        return bestSum;
    }

    private void walk(TreeNode node, int len, int sum) {
        if (node == null) return;
        len++;
        sum += node.val;
        if (node.left == null && node.right == null) {      // a leaf: compare with the board
            if (len > bestLen || (len == bestLen && sum > bestSum)) {
                bestLen = len;
                bestSum = sum;
            }
            return;
        }
        walk(node.left, len, sum);
        walk(node.right, len, sum);
    }
}

How long it takes: each node once, O(n). Extra room: only the call stack, O(h).

Watch out for

• Checking at empty children instead of at leaves. A node with one child is not the end of a path; only a node with no children is.
• Starting the best sum at 0 breaks trees with only negative numbers. Start at the smallest int, or let the first leaf set it because its length beats 0.
• An empty tree. Decide what to return (usually 0) and handle it before the walk.

What interviewers ask next

• Return the path itself, not only its sum. Keep the current path in a list and copy it when the best changes, or remember the best leaf and a parent map.
• The biggest sum of any root to leaf path, ignoring length. Same walk, compare only sums.
• Can you do it bottom up, without fields? Make each call return a pair (length, sum) of the best path below it, and pick between the left and right pair with the same rule.
• Do it level by level. With a queue holding (node, sum) pairs, the last row of the tree has the longest paths; take the biggest sum among the leaves of the last row.

Remember this

Grown-up words: the bottom of a slide is a leaf, carrying numbers down while going deep is a preorder depth first search, the board with the best ride is a pair of global variables, and the walk's waiting helpers are the call stack.