Binary Tree: Max Path Sum (approach and explanation)

Module: Binary Tree

You can refer to the Leetcode problem 124. Binary Tree Maximum Path Sum

In my personal opinion, this question has the ability to judge your analytical and tree traversal skills. You must give it a try before jumping onto solution.
By that you might get to know how ruthless this problem is. At the end of this article you would develop the thinking capability and would be able to solve problems like path-sum, longest-branch, diameter of a tree etc. See related problems at the end. Cheers!

Problem Statement

Given the root of a Binary Tree, return the maximum path sum of any non-empty path.

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.

Example 1:

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:

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.

Intuition

We first need to carefully understand the problem statement and note out some key points.

1. Path : In first attempt it would sound like usual root to leaf path, but that's a branch for any given root. A path in general is a chain of 1 or more adjacent(connected and contiguous) nodes. It, the path, may or may not include root itself. That's the essence of the question that it's asking for any path that gives us maximum sum(when values added).
2. Non-Empty Path : This makes sense as we are not going to count a nil path.
3. At most once : This must be taken into account that a valid path must not include a node more than once.

Now since we are clear that a path with max-sum may exist without the root itself, it means for whatever algo we deduce, we need to visit each node in recursion. May be our max path would be lying somewhere down. See below examples to make it more clear.

Although there several path that are possible out of these 5 nodes or 4 edges. Let's list them down:

Starting at node 2:

1. 2 : sum = 2
2. 2 <--> -3 : sum= -1
3. 2 <--> -3 <--> 3 : sum = 2
4. 2 <--> -3 <--> 3 <--> 4 : sum = 6
5. 2 <--> -3 <--> 3 <--> 5 : sum = 7

Starting at node -3:

1. -3 : sum = -3
2. -3 <--> 3 : sum = 0
3. -3 <--> 3 <--> 4 : sum = 4
4. -3 <--> 3 <--> 5 : sum = 5

Starting at node 3:

1. 3 : sum = 3
2. 3 <--> 4 : sum = 7
3. 3 <--> 5 : sum = 8

Starting at node 4:

1. 4 : sum = 4
2. 4 <--> 3 <--> 5 : sum = 12

Starting at node 5:

1. 5 : sum = 5

Note that the a path order does not matter while calculating the sum, so a path 3 -> 4 will be same as 4 ->3

Does it make any sense to return the max sum for path like 2 <--> -3 <--> 3 with sum as 2?
No! it's obvious that the output would be 12 for path 4 <--> 3 <--> 5, see nodes highlighted in green.

Let now try to build our logic now. We shall taking into consideration each obvious permutations.

1. No left/right sub-tree (Single node tree or a leaf node)

If you ever get your hands dirty with tree traversal, you might have encountered the situation where curr is pointing to left-most node or any leaf node.
We used to put this node onto stack (as it's not null) and after this, our curr would be pointing to it's left or right as per the order.

Remember, single node is also a valid path!

Now for path-sum, since we do not have anything as it's left or right, we would be returning the node value directly.

What if the left and right child exists? In that case we shall evaluate if that's profitable or not?

2. When sub-tree exists (Evaluating the Gain/Profit)

Before going to logic, can you tell us if we shall take -1 & -2 into account to get a max sum ? No! Why should we, because we are good with only node 1.
Adding -1 or -2 into the path would further decrease our max value, that's something like profit and loss. So how shall we program this logic?

What about this one?

Shall we add the node 3 now? In previous diagram, our max-sum was 1. In this, if we take the new node 3, our max sum becomes 2.
So our new path becomes 1 -> -2 -> 3 that results in a max sum of 2.

To add to your surprise, we are wrong here! That's something that we need to take care.
We would not be taking the path from node 1 to 3. If you look closely, only node 3 alone is making a greater max.
path 1 -> -2 -> 3 is less profitable as compared to path 3 only.

We can deduce some key points here:

• We need to get maximum sum for left child and right child. Let's create a function someMethodToGetMaximumSumFromTreeNode that would accept a TreeNode.

  int leftMax = someMethodToGetMaximumSumFromTreeNode(curr.left)

  int rightMax = someMethodToGetMaximumSumFromTreeNode(curr.right)

• If there are other branches to visit, we can not take both left and right or in other words we can not have 3 way path.
  So we should choose a maximum out of these left-max or right-max and combine this path with parent to get a path. Let's call it maxChildren

int maxChildren = Math.max(leftMax, rightMax)

• We need to check if adding left or right(whichever way is greater) to current would increase or path sum or decrease. How to do this? We need to use Math.max() function with left and right.

  int maxWithRoot = Math.max(curr.val, (curr.val + maxChildren))

• We also need to check if left and right together along with root form a greater value or not ? This is something adding all the nodes if a tree [1,2,3].
  Let's call this maxNode.

  int maxNode = Math.max(maxWithRoot, root.val + leftMax + rightMax)

• Last part for calculating the max sum is if already found a greater path sum or is this a new greater sum. We need to update our answer accordingly.

  maxSum = Math.max(maxSum, maxNode)

So that was all about evaluating the profitability and assigining bigger max to our answer.
But we have not worked on the return type and it's logic for function someMethodToGetMaximumSumFromTreeNode.

This function, for each tree node, evaluates the maximum path sum up-till(root must be included in path sum) the given root.
So for a tree [1, 2, 3], leftMax would be 2 and right max would be 3 and the return value would be maximum of 2 & 3 + root value.
Do we already have such logic? Yes! See maxWithRoot and this is what we would return in our function.

Note that, we are evaluating our answer in variable maxSum whereas the return value for the function is returned by maxWithRoot

Complexity Analysis

Time complexity: O(N), where N is number of nodes, since we visit each node not more than 2 times.

Space complexity: O(H), where H is a tree height, to keep the recursion stack. In the average case of balanced tree, the tree height H = logN, in the worst case of skewed tree, H=N.

program

class Solution {
  int maxSum = Integer.MIN_VALUE;

  public int maxPathSum(TreeNode root) {
    //recurse(root);
    getMaxPathSum(root);
    return maxSum;
  }

    int recurse(TreeNode root){

        if(root == null) return 0;

        int leftMax = recurse(root.left);
        int rightMax = recurse(root.right);

        int maxChildren =  Math.max(leftMax, rightMax);

        int maxWithRoot = Math.max(root.val, (root.val + maxChildren));

        int maxNode = Math.max(maxWithRoot, root.val + leftMax + rightMax);

        maxSum = Math.max(maxSum, maxNode);

        return maxWithRoot;

    }

    // Enhanced version of our logic
    private int getMaxPathSum(TreeNode root) {

        if (root == null) return 0;

        int leftMax = Math.max(0, getMaxPathSum(root.left)); // Take 0 instead of a negative left sum
        int rightMax = Math.max(0, getMaxPathSum(root.right)); // Take 0 instead of a negative right sum

        maxSum = Math.max(maxSum, (leftMax + rightMax + root.val));

        return Math.max(leftMax, rightMax) + root.val;
    }

}

Test cases

For this particular I have pled up few edge cases that you should try before submitting your soltution

[1]
[-1]
[1,null, 1]
[2, -1]
[2, -1, -2]
[1,2,3]
[1,2,3,1,3,2,null,1]
[3,9,20,null,null,15,7]
[1,-2,-3,1,3,-2,null,-1]
[-10,9,20,null,null,15,7]
[1,2,3,null, null,4,5,6,7,8,9,10]
[5,4,8,11,null,13,4,7,2,null,null,null,1]
[1,2,3,null, null, 4,5,6,7, null,8,9, null, 10, 11, null, null,12, 13, 14, null, 15, null,16, null, null, 17, null, null, 18, null]
[-1,null, -1,null, -1,null, -1,null, -1,null, -1,null, -1,null, -1,null, -1,null, -1,null, -1,null, -1,null, -1,null, -1,null, -1,null, -1,null, 16]

Related problems

• Path Sum
• Sum Root to Leaf Numbers
• Path Sum IV
• Longest Univalue Path
• Time Needed to Inform All Employees
• Diameter of Binary Tree

Problem Credit : leetcode.com