Solving Binary Tree Maximum Path Sum in JavaScript: Step-by-Step Guide

Introduction to Binary Tree Maximum Path Sum

The Binary Tree Maximum Path Sum problem is one of the most classic and challenging problems in tree-based algorithms. Given a binary tree where each node contains an integer value (which can be positive, negative, or zero), the task is to find the maximum sum of any path connecting nodes in the tree. A path in this context is defined as a sequence of nodes where each pair of adjacent nodes is connected by an edge, and no node appears more than once in the sequence.

This problem frequently appears in technical interviews at major tech companies and on platforms like LeetCode (Problem #124). Mastering it not only sharpens your understanding of tree traversal but also deepens your grasp of recursion, state management, and global vs. local variable handling in recursive functions.

What Makes It Tricky?

The difficulty lies in the fact that a valid path can take many shapes. It can be a single node, a path that goes strictly down one side, or a path that "bends" through a node, going down both its left and right subtrees. Unlike simple depth-first searches, you must consider both the possibility of extending a path upward and the possibility that the best path is entirely contained within a subtree.

Understanding the Problem Statement

Let's formalize the problem. You are given the root of a binary tree. Each node has three properties: val (the integer value), left (a reference to the left child or null), and right (a reference to the right child or null). You need to return the maximum possible sum of any path in the tree.

Consider this example tree:

      1
     / \
    2   3

The possible paths are: [1] (sum 1), [2] (sum 2), [3] (sum 3), [2, 1] (sum 3), [1, 3] (sum 4), and [2, 1, 3] (sum 6). The maximum path sum is 6.

Now consider a tree with negative values:

     -10
     /  \
    9   20
        / \
       15  7

Here, the best path is [15, 20, 7] with a sum of 42. Notice that this path does not include the root node, because including -10 would reduce the total sum.

Why This Problem Matters

Beyond its interview popularity, the Binary Tree Maximum Path Sum problem teaches several fundamental concepts that apply broadly in software engineering:

• Recursive thinking: Breaking a complex problem into smaller subproblems that mirror the original.
• Post-order traversal: Processing children before the parent, which is essential when you need information from both subtrees to make a decision at the current node.
• Distinguishing local vs. global optima: The best path through a node may not be the best path to return to its parent, because a parent can only extend one branch.
• Handling edge cases: Negative values, single-node trees, and skewed trees all require careful consideration.

These skills transfer directly to real-world scenarios such as evaluating expression trees, analyzing organizational hierarchies, and processing network topologies where you need to find optimal connected substructures.

Breaking Down the Approach

The key insight is to recognize that at each node, two different questions must be answered:

1. What is the maximum path sum that passes through this node and can be extended upward to its parent? This path can only include one of the two subtrees (or neither), because going up to the parent means you cannot bend through both children.
2. What is the maximum path sum that passes through this node as the "highest point" of the path? This path can include both the left and right subtrees, forming a V-shape through the node.

The answer to the first question is what we return from the recursive function (so the parent can use it). The answer to the second question is what we use to update a global maximum, because such a path cannot be extended further upward.

The Recursive Formula

For any given node, let leftGain be the maximum path sum starting from the left child and going downward (or 0 if it is negative, because we would rather not include that subtree at all). Similarly, let rightGain be the maximum path sum starting from the right child and going downward.

The maximum path sum that bends through the current node is:

currentPathSum = node.val + leftGain + rightGain

We update the global maximum with this value. Then, the value we return to the parent is:

return node.val + Math.max(leftGain, rightGain)

This represents the best single-branch path extending upward from this node.

Implementing the Solution in JavaScript

Let's now translate this logic into JavaScript code. First, we define the tree node structure:

// Definition for a binary tree node.
function TreeNode(val, left, right) {
  this.val = (val === undefined ? 0 : val);
  this.left = (left === undefined ? null : left);
  this.right = (right === undefined ? null : right);
}

Next, here is the complete solution:

/**
 * @param {TreeNode} root
 * @return {number}
 */
function maxPathSum(root) {
  // Initialize the global maximum to negative infinity
  // so that any real path sum will be larger.
  let maxSum = -Infinity;

  /**
   * Recursive helper function that returns the maximum
   * single-branch path sum starting from the given node.
   * @param {TreeNode|null} node
   * @return {number}
   */
  function maxGain(node) {
    if (node === null) {
      return 0;
    }

    // Recursively compute the max gain from left and right subtrees.
    // If the gain is negative, we treat it as 0 because including
    // a negative-sum branch would only reduce the total.
    const leftGain = Math.max(maxGain(node.left), 0);
    const rightGain = Math.max(maxGain(node.right), 0);

    // The path sum if this node is the highest point of the path.
    const currentPathSum = node.val + leftGain + rightGain;

    // Update the global maximum if this path is better.
    maxSum = Math.max(maxSum, currentPathSum);

    // Return the best single-branch path to the parent.
    return node.val + Math.max(leftGain, rightGain);
  }

  maxGain(root);
  return maxSum;
}

Walking Through the Code

Let's trace through the algorithm using the second example tree (-10, 9, 20, 15, 7):

1. We call maxGain(-10), which recursively calls maxGain(9) and maxGain(20).
2. maxGain(9) has no children, so leftGain = 0 and rightGain = 0. The current path sum is 9, so maxSum becomes 9. It returns 9 to the parent.
3. maxGain(20) calls maxGain(15) and maxGain(7).
4. maxGain(15) returns 15, and maxGain(7) returns 7. Both update maxSum but neither exceeds 15 yet.
5. Back at node 20: leftGain = 15, rightGain = 7. The current path sum is 20 + 15 + 7 = 42. maxSum becomes 42. It returns 20 + 15 = 35 to the parent.
6. Back at root -10: leftGain = 9, rightGain = 35. The current path sum is -10 + 9 + 35 = 34. maxSum stays at 42. It returns -10 + 35 = 25.
7. The final answer is 42.

Testing the Solution

To verify correctness, let's build the example trees and run the function:

// Helper function to build a tree from an array (level-order).
function buildTree(arr) {
  if (arr.length === 0 || arr[0] === null) return null;
  const root = new TreeNode(arr[0]);
  const queue = [root];
  let i = 1;
  while (queue.length > 0 && i < arr.length) {
    const node = queue.shift();
    if (i < arr.length && arr[i] !== null) {
      node.left = new TreeNode(arr[i]);
      queue.push(node.left);
    }
    i++;
    if (i < arr.length && arr[i] !== null) {
      node.right = new TreeNode(arr[i]);
      queue.push(node.right);
    }
    i++;
  }
  return root;
}

// Test case 1: Simple tree
const tree1 = buildTree([1, 2, 3]);
console.log(maxPathSum(tree1)); // Output: 6

// Test case 2: Tree with negative root
const tree2 = buildTree([-10, 9, 20, null, null, 15, 7]);
console.log(maxPathSum(tree2)); // Output: 42

// Test case 3: Single node
const tree3 = buildTree([5]);
console.log(maxPathSum(tree3)); // Output: 5

// Test case 4: All negative values
const tree4 = buildTree([-3, -1, -2]);
console.log(maxPathSum(tree4)); // Output: -1

// Test case 5: Skewed tree
const tree5 = buildTree([2, -1, null, -2, null, -3]);
console.log(maxPathSum(tree5)); // Output: 2

Notice test case 4 carefully. When all values are negative, the Math.max(gain, 0) logic would turn every child gain into 0, but the node's own value is still considered. The best path is simply the single node with the largest value, which is -1. This is why initializing maxSum to -Infinity rather than 0 is critical.

Complexity Analysis

Understanding the time and space complexity of this solution is essential for evaluating its efficiency:

• Time Complexity: O(n) — We visit each node exactly once during the post-order traversal, where n is the total number of nodes in the tree. Each visit performs constant-time operations.
• Space Complexity: O(h) — The space is determined by the recursion stack depth, which equals the height h of the tree. In the worst case (a completely skewed tree), this is O(n). In a balanced tree, it is O(log n).

This is optimal for the problem, as you must examine every node at least once to determine the maximum path sum.

Best Practices and Common Pitfalls

When implementing this solution, keep the following best practices in mind:

1. Initialize the Global Maximum Correctly

Always initialize maxSum to -Infinity (or Number.NEGATIVE_INFINITY), never to 0. Since node values can be negative, a valid path sum might be negative, and initializing to 0 would produce incorrect results for all-negative trees.

2. Clamp Negative Gains to Zero

The line Math.max(maxGain(child), 0) is crucial. It ensures that we never extend a path into a subtree that would reduce the total sum. Without this clamping, the algorithm would incorrectly include negative branches and produce suboptimal results.

3. Avoid Using a Class-Level Variable in Interviews

In the solution above, we used a closure variable maxSum. In an interview setting, some candidates use a class field or an outer variable. Both approaches work, but the closure approach keeps the state encapsulated within the function, which is cleaner and avoids polluting the global scope.

4. Do Not Return the Bent Path Upward

A common mistake is returning node.val + leftGain + rightGain to the parent. Remember, a parent can only extend one branch. If you return the bent path, the parent would incorrectly assume it can extend both sides, leading to invalid paths that revisit nodes.

5. Handle Null Nodes Explicitly

Always check for null at the start of the recursive function. Forgetting this leads to runtime errors when accessing node.val or node.left on a null reference.

Alternative Approaches

While the recursive post-order traversal is the most elegant and commonly accepted solution, there are alternative approaches worth knowing:

Iterative Post-Order Traversal

If recursion depth is a concern (for extremely deep trees), you can implement the same logic iteratively using an explicit stack. The logic remains identical, but you manually manage the traversal order:

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

  let maxSum = -Infinity;
  const stack = [];
  const gains = new Map();
  stack.push(root);

  while (stack.length > 0) {
    const node = stack[stack.length - 1];

    if (
      (node.left === null || gains.has(node.left)) &&
      (node.right === null || gains.has(node.right))
    ) {
      stack.pop();
      const leftGain = node.left ? Math.max(gains.get(node.left), 0) : 0;
      const rightGain = node.right ? Math.max(gains.get(node.right), 0) : 0;
      const currentPathSum = node.val + leftGain + rightGain;
      maxSum = Math.max(maxSum, currentPathSum);
      gains.set(node, node.val + Math.max(leftGain, rightGain));
    } else {
      if (node.right) stack.push(node.right);
      if (node.left) stack.push(node.left);
    }
  }

  return maxSum;
}

This approach uses a Map to store the computed gain for each node, simulating the return values of the recursive calls. It avoids potential stack overflow errors on very deep trees, though it is more verbose.

Real-World Applications

The pattern used in this solution — computing a local result while tracking a global optimum — appears in many practical scenarios:

• Network routing: Finding the path with maximum bandwidth or minimum latency between nodes in a network topology.
• Financial analysis: Evaluating hierarchical investment portfolios where each node represents an asset class with a return value, and you want to find the best-performing connected sub-portfolio.
• Game AI: Evaluating decision trees in game theory, where each node represents a game state with a score, and you need to find the most advantageous sequence of moves.
• Org chart analysis: Finding the most productive team structure in a company hierarchy based on individual performance scores.

Conclusion

The Binary Tree Maximum Path Sum problem is a powerful exercise in recursive problem-solving that rewards careful thinking about what information flows up the recursion stack versus what is tracked globally. By separating the concept of a "bent path" (which updates the global maximum) from a "single-branch path" (which is returned to the parent), the solution elegantly handles all edge cases including negative values, single-node trees, and skewed structures. The O(n) time complexity makes it efficient for large trees, and the recursive implementation is concise enough to write confidently in an interview setting. Mastering this problem not only prepares you for technical interviews but also builds a mental model that applies to a wide range of tree and graph optimization challenges you will encounter throughout your career.