Leetcode diary: 124. Binary Tree Maximum Path Sum

#javascript #algorithms #devjournal #motivation

This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

link

This problem! I have solved this years ago when I was preparing back then, but I never really document the logic for this, so this is what is long over due!

The description is simple: given a binary tree, not binary search tree, return the number of the maximum sum path.

Specifically, a path in the definition of the question is just a straight line from node A to node B, and all the sums in between. However, it cannot have a divergent path. A small gotcha that ruins countless lives :(

The above is the test case that demonstrate what a path means well.
Specifically, look at the left subtree. The maximum path sum for the subtree is 4 + 1 + 3 = 8. However, the maximum path sum for the entire tree is 10 + 4 + 1, because we can only have a non-divergent path.

So the question is how do you handle that which part of the subtree gets passed on? Since there is no divergent paths, the possibility can only be:
1.) left + node.val
2.) right + node.val
3.) node.val
So one of these 3 will always be the return value of a given node.

Now another thing that needs to be mentioned is that you have to do dfs for this problem. You probably could BFS it...but I don't know how and it's a lot less intuitive doing so. DFS is much better, because the incremental problem solving nature of DFS. So you can work from the smallest subtree all the way up to the root to find the max path sum.

However, that's not it for the problem has to challenge you!
consider this case:

it should be apparent that the answer is 140, and you should notice that the -90 node kind of "cut off" the path from progressing because adding the -90 node just decrease the sum too much. In other words, there could be cases where the maximum sum is inside a subtree somewhere and everything else is just noise that makes us difficult to find it.

So how do we handle that? Luckily for us, DFS makes sure we travel and expand from the smallest subtree to the biggest subtree. So with DFS, we are sure to find the subtree that has the maximum path sum. The question just becomes how do we remember the value.

Remembering the value is easy right? We can just have a global variable to the function and remember the maximum value of at any point like:



function maxPathSum (root) {
    let globalMax = -Infinity;

    function findMaxSum(node) {
          ...
          globalMax = Math.max(...other_values, globalMax)
    }

    findMaxSum(root)
    return globalMax
}

That's it, that solves our problem of remembering the max. However, what could be the values for other_values ?
Well, we don't know right? it could be:
1.) the node itself, evidently true for the leaf nodes
2.) node + left
3.) node + right
4.) node + left + right
The tricky part is probably node + left + right, because it feels like a "divergent" path, but that's not so in the perspective of the the current subtree itself right? It is the same at the parent + node + node.left.

So the trickiest part about this problem is that you are supposed to separate out conceptually what you can return from the current node vs what is the maximum of the current node. A mental hurdle has to be overcome, because we are very used to care about and return only a single value from a node. However in this case, we care about two possible conceptual maximum for the node:
1.) the current path sum for the node, the other_values array
2.) the current maximum path sum you are allowed to propagate upward for the parent node to consume. This is the first part of my explanation.
The annoying thing about it is that the difference is one can contain left + node + right, while the other cannot. So everything feels so conceptually the same that it is difficult to tease out exactly what can be returned and why. Hopefully I've done a good job explaining the differences and reasoning.

The full code is below:



var maxPathSum = function(root) {
    let max = -Infinity;

    function findMaxSum(root) {
        if(!root) return -Infinity;

        const left  = findMaxSum(root.left);
        const right = findMaxSum(root.right);
        const leftAndVal  = left + root.val;
        const rightAndVal = right + root.val;
        const all = left + right + root.val;

        let currentMax = Math.max(
            leftAndVal, rightAndVal, all, root.val
        );

        max = Math.max(currentMax, max);
        return Math.max(
            root.val,
            leftAndVal,
            rightAndVal,
        )        
    }

    findMaxSum(root);
    return max;
};

Quick note for the use of Infinity. I've seen in other problems that people use Number.MAX_SAFE_INTEGER or the min. However that would not work in this case because adding/subtracting past the limit will return NaN, which breaks Math.max and will only returns NaN for you.

Let me know anything on your mind after reading through this, THANKS!