3.6 Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

Logical Steps

For any node, the max path sum in binary tree could be in one of the two cases:

1. Max path sum from node to root in left tree + max path sum from node to root in right tree + current node value
2. Max node 2 node max sum in left tree or right tree

As shown above, for each node in each recursive iteration, we must compute the max path from node to root in left and right path. Also, in one of the two cases:

1. Max path sum from node to root in left tree, or max path sum from node to root in right tree, plus current node value
2. If current node to root is negative value and doesn't contribute to node 2 node value, pick 0 instead of max node to root value

Code Implementation

/**
* constructe a return type with
* max path sum to root in current node
* and max path sum to node in current node
*/
class ReturnType{
    int maxToRoot = 0;
    /** set maxToNode to negative infinity
    * in order to avoid the case when 
    * root value is nagetive and first maxToNode
    * pick up zero
    */
    int maxToNode = Integer.MIN_VALUE;

    ReturnType(){}
    ReturnType(int maxToRoot, int maxToNode) {
        this.maxToRoot = maxToRoot;
        this.maxToNode = maxToNode;
    }
}

public ReturnType helper(TreeNode root) {
    // base case: root is null
    if (root == null)
        return new ReturnType();

    // divide
    ReturnType left = helper(root.left);
    ReturnType right = helper(root.right);

    // update max path node to root

    /** since we are going from left/right node to root
    * root.val has to be taken for sure
    */
    int maxToRoot = Math.max(left.maxToRoot, right.maxToRoot)
        + root.val;

    // if maxToRoot is negative, than take 0 (stay at root)
    maxToRoot = Math.max(0, maxToRoot);

    // update max path node 2 node (maxToNode from left and right)
    int maxToNode = Math.max(left.maxToNode, right.maxToNode);

    // Take current node value and maxToRoot from left and right
    maxToNode = Math.max(maxToNode,
        left.maxToRoot + right.maxToRoot + node.val);

    return new ReturnType(maxToRoot, maxToNode);
}

Common Mistakes

1. Decide max path node 2 root from taking current node value or not instead of left and right tree

    /** since this is the max path sum from current node to root
    * we have to take current root in order to make next 
    * iteration work. 
    * And also, this value is decided by child
    * nodes, instead of parent nodes, so left and right must be
    * considered
    */
    int maxToRoot = Math.max(maxToRoot, maxToRoot + curr.val);