Maximum Path Sum in Binary Tree

Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along with the parent-child connections. The path must contain at least one node and does not need to go through the root. For example

Example 1:

Input: [1,2,3]
   
       1
      / \
     2   3

Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

If you want to watch the video, you can check here:

Maximum Path Sum: thought process

We already have solved quite a few problems on path sum in binary trees like finding the sum of all paths, find a path with a given sum, find sum with maximum sum. Difference between problems we saw before and this one is that in this question the path may not pass through the root. The path here is not defined between root and leaf node, but any two nodes. In example 2, the maximum path sum is 15->20->7, which is the path between node 15 and node 7.

A lot of things are going on here, let’s decouple some things. First of all, we have to keep a global maximum. Second, the root may be part of the maximum path or it may not be.
The first problem is simple to solve, we will keep a global variable (I know, we can change it with an array param). For the second problem, if we do not include node in the path, that means we will not be including any node in the subtree rooted at this node, because a path has to be continuous and we cannot skip the node.

maximum path sum in binary tree

Now, we have to decide when to include the node in the path and when not to.

At each node, we are returning the maximum sum we can get from the subtree under this node.

Each node actually does two things: When processing the final result maxValue, the node is treated as the highest point of a path. When calculating its return value, it is only part of a path (left or right part), and this return value will be used to calculate the path sum of other paths with some other nodes(above the current one) as their highest point.

If the maximum sum which can be achieved from the tree under the node is negative, there is no point including any path which crosses this node as it will lead to the smaller global sum, hence we mimic that making sum received from such a node as zero.
In example 2, adding -10 to the path sum (9) of the left subtree makes it negative, there is no point connecting the left subtree path (09 + -10) to the right subtree path as it will lead to a smaller sum.

At every node, we update the maximum sum we can get at that node, by adding left path sum, right path sum, and root value. We check if that is greater than known max, we update the global max.


After updating the global max, we have to return the maximum sum we can achieve at the node, by getting the max sum of left subtree and right subtree and adding root.value to it. To the upper layer(after return statement), we cannot choose both left and right brunches, so we need to select the larger one, so we use max(left, right) + node.val to prune the lower brunch.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return res;
    }
    private int dfs(TreeNode node) {
        
        if(node == null) return 0;
        
        //Get maximum sum on the left subtree
        int l = Math.max(0,dfs(node.left));
        //Get maximum sum on right subtree,
        // if negative, make it zero
        int r = Math.max(0,dfs(node.right));
        
        //Update the global value.
        res = Math.max(l + r + node.val, res);
        
        //Return max sum of the path including this node.
        return Math.max(l, r) + node.val;
    }
}

As we traverse each node of the tree, the overall complexity of the implementation is O(n).