Max Path Sum Between Two Leaves

Problem Overview

Any path between two leaves turns around at exactly one node, and that node must have both a left and a right child.

Intuition

Any path between two leaves turns around at exactly one node, and that node must have both a left and a right child. So for every node it is enough to know the best sum of a path going down from it to a leaf. A node with two children joins its best left and best right downward paths into a leaf to leaf candidate. A node with one child is not a leaf, so its downward path must continue through that child even when the sum gets worse.

Algorithm

1Return -1 for an empty tree.
2List the nodes in level order and remember each child position. Every parent appears before its children.
3Walk that list backwards. A leaf has a downward sum equal to its value.
4A node with two children updates the answer with its value plus both children sums, and its downward sum is its value plus the larger child sum.
5A node with one child has a downward sum of its value plus that child sum.
6If no node had two children, there are fewer than two leaves, so return -1. Otherwise return the best candidate.

Example Walkthrough

Input: root = [3,4,5,-10,4]

1. The leaves -10, 4, and 5 return their own values.
2. Node 4 joins -10 and 4 for a candidate of -2, and passes up 4 + 4 = 8.
3. Node 3 joins 8 and 5 for a candidate of 16, which is the best leaf to leaf path 4, 4, 3, 5.

Output: 16

Common Pitfalls

• A root with only one child is not a leaf. Treating it as one allows paths that the problem does not count.
• A node with one child must pass through it. Taking 0 for the missing side would end a path at a node that is not a leaf.
• Values can be negative, so start the best candidate at the smallest integer rather than 0.
• A recursive post order walk can overflow the stack on a skewed tree. Walking the level order list backwards avoids recursion.

Max Path Sum Between Two Leaves.java

Java

// Approach: For every node, down is the best sum of a path from that node to
// a leaf below it. A node with two children can join its best left and best
// right downward paths into a leaf to leaf path. A node with one child must
// extend through that child, because it is not a leaf. Nodes are listed in
// level order, which places every parent before its children, so walking
// that list backwards computes each node after both of its children with no
// recursion. A leaf has no children, so a root with one child is not a leaf.
// Without any node that has two children (including an empty tree), there
// are fewer than two leaves and the answer is -1.
// Complexity: O(n) time, O(n) extra space.
import java.util.ArrayList;
import java.util.Arrays;

class Node {
    int data;
    Node left, right;

    Node(int item) {
        data = item;
        left = right = null;
    }
}

class Solution {
    public int maxPathSum(Node root) {
        if (root == null)
            return -1;

        ArrayList<Node> order = new ArrayList<>();
        int[] leftIdx = new int[16];
        int[] rightIdx = new int[16];
        order.add(root);

        for (int k = 0; k < order.size(); k++) {
            if (k == leftIdx.length) {
                leftIdx = Arrays.copyOf(leftIdx, k * 2);
                rightIdx = Arrays.copyOf(rightIdx, k * 2);
            }
            Node u = order.get(k);
            leftIdx[k] = -1;
            rightIdx[k] = -1;
            if (u.left != null) {
                leftIdx[k] = order.size();
                order.add(u.left);
            }
            if (u.right != null) {
                rightIdx[k] = order.size();
                order.add(u.right);
            }
        }

        int n = order.size();
        int[] down = new int[n];
        int best = Integer.MIN_VALUE;
        boolean found = false;
        for (int k = n - 1; k >= 0; k--) {
            int data = order.get(k).data;
            int l = leftIdx[k];
            int r = rightIdx[k];
            if (l >= 0 && r >= 0) {
                best = Math.max(best, data + down[l] + down[r]);
                found = true;
                down[k] = data + Math.max(down[l], down[r]);
            } else if (l >= 0) {
                down[k] = data + down[l];
            } else if (r >= 0) {
                down[k] = data + down[r];
            } else {
                down[k] = data;
            }
        }

        return found ? best : -1;
    }
}

Was this solution helpful?