Binay Tree Max Path Sum

When it comes to solving algorithm problems, I've never found the brute force approach of solving a lot of problems and expecting my brain to pick up common themes and patterns helpful. Rather I rely more on an intuitive understanding of data structures and algorithms. This approach helps me see the mapping between the problem and the solution on a high level and the unique characteristic of a data structure or an algorithm that fit the solution.

Max Path Sum is a fairly easy problem to solve if you have basic intuition around recursion patterns in Binary Trees. Here, we are not merely going to focus on the solution. Rather, we will be having an exercise in thinking about solving data structures and algorithm problems.

Let's analyze the question and establish the core facts of the problem.

Path - What is a path in a binary tree? A valid path contains any set of nodes that don't end up circular. The root doesn't have to be in this set. Moreover, any node can be part of two potential paths at the same time.

A path involving both of its subtrees but not involving its parent node.
A path involving its parent node but only one of its subtrees.

The reason is a path can't have branches. When we decide on adding a new node to the path, a third branch is added. If we add the new node to the path, we let go of one of the subtrees of the current node. Else we keep both the subtrees and let go of this new node. We make this decision every time we visit a node while traveling through the tree.

Global State - Since we start at the root of the tree and the root doesn't have to be in the final path, the max path sum could exist in any of the subtrees. Also, this logic will be applied to all the nodes except the leaf nodes. This requires us to maintain a global variable containing the current max sum at any point in the traversal. The two subtrees can update this variable independently. FYI, this kind of operation is called a reduction operation in computer science as we are reducing a collection to a terminal integer value.

Max sum - The max path sum of the tree is recursively built up by the max contribution provided by both subtrees of a node. Either we take both these contributions along with the node's weight or we take the max of these contributions along with the node's weight if the parent node is not negative.

After establishing these facts, we have a lot of intuition for our solution. Since we are using recursion, we have to find our base cases. Base cases almost always depend upon the nature of the required output. Since the max path sum of the tree depends upon the max path sum of its subtrees, we will build the solution in a bottom-up manner. The lowest path sum contributed by any node is 0. That means, our base cases involve null nodes which are the subtrees of the leaf nodes.

Let's start developing the algorithm:

We have a maxContrib function which gives us the current node's max contribution towards the max path sum. If the node is null, we return 0 and this becomes our base case. The recursion stack unwinds here.
```
  let maxPathSum = Infinity * -1;

  function maxContrib(root) {
    if (root === null) return 0;

    // remaining solution
  }
```

To calculate the max contribution of the current node, we need to calculate the max contribution provided by its left and right subtrees. Hence, we store these two sums by recursing on both subtrees. We also need to check if the contribution provided by the subtrees is not negative. If the value is negative, we store it as 0. This basically means that the entire subtree is out of the final max path sum calculation.

  let maxPathSum = Infinity * -1;

  function maxContrib(root) {
    if (root === null) return 0;

    let maxContribLeft = maxContrib(root.left);
    let maxContribRight = maxContrib(root.right);

    let maxLeftSubtree,
      maxRightSubtree = 0;

    if (maxContribLeft > 0) maxLeftSubtree = maxContribLeft;
    if (maxContribRight > 0) maxRightSubtree = maxContribRight;

    // remainig solution
  }

Before returning the max contribution of the current node, we calculate a fallback path sum that involves the current node and its subtrees. We update the max path sum if it is greater than the current max path sum. We do this to ensure we have our final solution if the parent node and its parent node and so on end up not contributing towards the max path sum. Again, we update these global values while visiting every node in the tree except for the leaf nodes.

Finally, we check if the weight of the current node is not negative. If it is, then we return the max of the max contribution by both the subtrees of the current node. If not, then we also add the weight of the current node.

  let maxPathSum = Infinity * -1;

  function maxContrib(root) {
    if (root === null) return 0;

    let maxContribLeft = maxContrib(root.left);
    let maxContribRight = maxContrib(root.right);

    let maxLeftSubtree,
      maxRightSubtree = 0;

    if (maxContribLeft > 0) maxLeftSubtree = maxContribLeft;
    if (maxContribRight > 0) maxRightSubtree = maxContribRight;

    let fallbackPathSum = root.weight + maxLeftSubtree + maxRightSubtree;

    maxPathSum = Math.max(maxPathSum, fallbackPathSum);

    if (!root.data) return Math.max(maxLeftSubtree, maxRightSubtree);
    else return root.weight + Math.max(maxLeftSubtree, maxRightSubtree);
  }

We arrive at the max path sum of the tree stored in the global variable maxPathSum when we reach the root node. At this point, the recursion stack is unwinded completely.

The takeaway here is that once we establish all the facts hidden in the problem, the solution gets a bit easier to deduce. Especially, when we are working with a data structure that has a lot of usage patterns like trees. Rather than brute forcing our way through all the patterns, we can choose one that naturally follows the problem. Here the base case required the nodes with a path sum contribution of 0, so we started from the leaf nodes in a bottom-up manner.

Another useful technique is to see if a real-world metaphor can help us reason about the problem at any step. Check out the following metaphor where we reason about the max path sum in terms of negotiation.

Metaphor

The key decision about the max path sum can be thought of as a communication between the current node and its parent node. The current node negotiates the fallback value of the max path sum with its parent node in case the parent node ends up not contributing.

let fallbackPathSum = root.weight + maxLeftSubtree + maxRightSubtree;

On the other hand, the current node hands its contribution to the ongoing path with its parent node, in case the parent node ends up contributing.

if (!root.data) return Math.max(maxLeftSubtree, maxRightSubtree);
else return root.weight + Math.max(maxLeftSubtree, maxRightSubtree);

Since we are trying to maximize a number, either we choose the weight at a node or we don't. This decision manifests in the problem by overriding the max path sum if the fallback path sum contribution of the current node is greater than the existing value.

In short, by choosing one branch of the path (the parent node), we let go of the other branch (one of the subtrees with a lower contribution) and vice-versa.

Hope you liked this exercise in thinking. In my opinion, approaching problems like this builds up our intuition faster compared to the brute force approach of solving a lot of problems.

The intuition behind the Binary Tree Max Path Sum problem