Problem

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node’s values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Examples

Example 1:

1
2
3

       1
      / \
     2   3

1
2
3

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

1
2
3
4
5

     -10
      / \
     9   20
        /  \
       15   7

1
2
3

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Solution

Method 1 - DFS

For each node, there are four possible paths for the maximum path sum:

  1. Only the node itself
  2. The maximum path through the left child plus the node
  3. The maximum path through the right child plus the node
  4. The maximum path through the left child, the node, and the right child

The key is to track these four paths and select the highest value at the end.

Note

It is important to understand that each subtree’s root must return the maximum path sum that includes at most one child. This is necessary for the call to the parent function. In the code below, this sum is called maxOne and it is what the recursive function returns.

Why don’t we return the sum of node.val + node.left + node.right (named currTwo) in the last line? Including currTwo in the maxPathSum would violate the principle that each node can be traversed only once. Since it is impossible to traverse from node->left->right->node’s parent without revisiting the node itself, we cannot include currTwo in the return value.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public int maxPathSum(TreeNode root) {
	int max[] = new int[1];
	max[0] = Integer.MIN_VALUE;
	calculateSum(root, max);
	return max[0];
}

public int calculateSum(TreeNode root, int[] max) {
	if (root == null) return 0;

	int leftMax = calculateSum(root.left, max);
	int rightMax = calculateSum(root.right, max);
	
	int maxOne = Math.max(root.val, root.val + Math.max(leftMax, rightMax));
	
	int currTwo = leftMax + root.val + rightMax;

	max[0] = Math.max(max[0], Math.max(maxOne, currTwo));

	return maxOne;
}
 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

public int calculateSum(TreeNode root, int[] max) {
	if (root == null) return 0;

	int left = calculateSum(root.left, max);
	int right = calculateSum(root.right, max);

	int maxOne = Stream.of(root.val, root.val + left, root.val + right).max().getInteger();
	
	int currTwo = leftMax + root.val + rightMax;

	max[0] = Stream.of(max[0], maxOne, currTwo).max().getInteger();

	return maxOne;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public class BinaryTreeMaximumPathSum {
    private int maxSum;
    public int maxPathSum(TreeNode root) {
        maxSum = Integer.MIN_VALUE;
        maxSumHelper(root);
        return maxSum; // as maxSum will always store the result
    }

    public int maxSumHelper(TreeNode root) {
		
		// base case
        if (root == null) return 0; 
		
		// recursing through left and right subtree
        int leftMax = maxSumHelper(root.left);
        int rightMax = maxSumHelper(root.right);

		// finding all the four paths and the maximum between all of them
        int maxRightLeft = Math.max(leftMax, rightMax);
        int maxOne = Math.max(root.val, (root.val + maxRightLeft));
        int maxAll = Math.max(maxOne, leftMax + rightMax + root.val);
		
		// Storing the result in the maxSum holder
        maxSum = Math.max(maxSum, maxAll);
		
		// returning the value if root was part of the answer
        return maxOne;

    }
}

Examples

Example 1

Our goal is to find the maximum path sum. Now consider the following example.

1
2
3

   10
  /  \
null null

In this simple case we know that the max sum would be just the root node itself and the answer would be 10. So fo all leaf nodes the max sum path is the value of the node itself.

Example 2

Now let’s consider the following example.

1
2
3

   20
  /  \
10    30

Here there are multiple possibilities and we need to take care of the following FOUR PATHS that could be our max.

  1. The root iself : 20
  2. The root with the maximum from it’s left subTree : = 10 + 20
1
2
3

    	20
    	/
      10
  1. The root with the maximum from it’s right subTree : = 30 + 20
1
2
3

		20
		  \
	       30
  1. The root with it’s left, right and itself = 60
1
2
3

   	 20
   	 / \
    10  30

In case you are wondering why we did not choose the root.left (10) or root.right(30) alone in the calculation ( like I wondered ), that’s because we would have already computed the result of it as a node in our recursion separately.