Binary Tree Maximum Path Sum

Question (LC.124)

Given the root of a binary tree, find the maximum path (connected by any start node and end node). Return the sum of that path.

Example

I: [1,2,3,4,5,6,7]
O: 1+2+3+4+5+6+7=18
I: [2,-25,4,10,20,5,6,7,11]
O: 7+10+11=28
I: []
O: -INF

Approach

We can apply a simple greedy approach. If the a local connected path has the largest sum, then we can simply just keep it until we find one beats it farther up. Each subproblem needs to return two pieces of information - the local connected max and the path max that can be connected in the future. D&C is the perfect candidate for perform this kind of work. Since we want to get some information from the left subtree and some information from the right subtree and then process by the root. The base case will just be (-INF,-INF) since no maximum path can be found.

Code

static final int NNF = Integer.MIN_VALUE;

private class PathType {
    int pathMax;
    int connectMax;
    public PathType(int path, int connect) {
        pathMax = path;
        connectMax = connect;
    }
}

public int maxPathSum(TreeNode root) {
    return pathHelper(root).connectMax;
}

private PathType pathHelper(TreeNode root) {
    // base case
    if (root == null) {
        return new PathType(NNF, NNF);
    }
    // divide
    PathType left = pathHelper(root.left);
    PathType right = pathHelper(root.right);
    // merge
    // 3 cases connect left, connect right, connect neither
    int pathMax = Math.max(Math.max(left.pathMax, right.pathMax), 0) + root.val;
    // 4 cases connect both, connect only left, connect only right, connect neither (null case)
    int localMax = Math.max(left.pathMax, 0) + // 0 to cut that branch off
                   root.val +
                   Math.max(right.pathMax, 0);    
    // we always want to pass along the current pathMax
    // but for connectMax, we want to pass along the greatest
    int connectMax = Math.max(localMax, Math.max(left.connectMax, right.connectMax));
    return new PathType(pathMax, connectMax);
}

Time Complexity

Traversing through the entire tree O(#nodes)