Maximum Path Sum in Binary Tree in DSA Javascript

Mental Model

Find the highest sum you can get by traveling along connected nodes in a tree, where the path can start and end anywhere.

Analogy: Imagine climbing a mountain trail that can go up and down, and you want to find the highest total elevation gain on any path you choose, not necessarily from base to peak.

      [10]
      /   \
   [2]     [10]
   / \       \
 [20] [1]    [-25]
              /   \
           [3]     [4]

Dry Run Walkthrough

Input: Binary tree with nodes: 10, 2, 10, 20, 1, -25, 3, 4

Goal: Find the maximum path sum anywhere in the tree

Step 1: Start at leaf node 20, max path sum is 20

20 (leaf) -> max path sum = 20

Why: Leaf nodes have max path sum equal to their own value

Step 2: At node 2, calculate max path sum including left child 20 and right child 1

2 -> left max = 20, right max = 1, max path through 2 = 2 + 20 + 1 = 23

Why: Path can go through node 2 connecting left and right children

Step 3: At node -25, calculate max path sum including children 3 and 4

-25 -> left max = 3, right max = 4, max path through -25 = -25 + 3 + 4 = -18

Why: Negative node reduces sum, but children add positive values

Step 4: At right child 10 (right of root), max path sum is max of 10 and 10 + max child (-25 subtree max is negative)

10 -> max path sum = 10 (ignore negative child)

Why: Ignore negative sums to maximize path

Step 5: At root 10, calculate max path sum including left max 23 and right max 10

10 -> left max = 23, right max = 10, max path through 10 = 10 + 23 + 10 = 43

Why: Path can go from left child through root to right child

Step 6: Compare all max sums found: 20, 23, -18, 10, 43; choose maximum 43

Maximum path sum = 43

Why: Final answer is the highest sum found anywhere in the tree

Result:

Maximum path sum = 43

Annotated Code

DSA Javascript

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

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

  function helper(node) {
    if (node === null) return 0;

    // Recursively get max path sum from left and right children
    const leftMax = Math.max(helper(node.left), 0); // ignore negative sums
    const rightMax = Math.max(helper(node.right), 0);

    // Calculate max path sum passing through current node
    const currentSum = node.val + leftMax + rightMax;

    // Update global maxSum if currentSum is higher
    maxSum = Math.max(maxSum, currentSum);

    // Return max sum path going down from current node
    return node.val + Math.max(leftMax, rightMax);
  }

  helper(root);
  return maxSum;
}

// Build tree from dry run example
const root = new TreeNode(10,
  new TreeNode(2,
    new TreeNode(20),
    new TreeNode(1)
  ),
  new TreeNode(10,
    null,
    new TreeNode(-25,
      new TreeNode(3),
      new TreeNode(4)
    )
  )
);

console.log(maxPathSum(root));

if (node === null) return 0;

stop recursion at leaf's child

const leftMax = Math.max(helper(node.left), 0);

get max path sum from left child, ignore negative sums

const rightMax = Math.max(helper(node.right), 0);

get max path sum from right child, ignore negative sums

const currentSum = node.val + leftMax + rightMax;

calculate max path sum passing through current node

maxSum = Math.max(maxSum, currentSum);

update global max if current path sum is higher

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

return max path sum going down from current node

Output

43

Complexity Analysis

Time: O(n) because we visit each node once in the tree

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Naive approach might try all paths explicitly, costing O(n^2) or more; this uses recursion to compute max sums efficiently

Edge Cases

Empty tree (root is null)

Returns -Infinity or 0 depending on implementation; here returns -Infinity as no nodes exist

DSA Javascript

if (node === null) return 0;

Tree with all negative values

Ignores negative child sums but still returns the maximum single node value

DSA Javascript

const leftMax = Math.max(helper(node.left), 0);

Single node tree

Returns the value of the single node as max path sum

DSA Javascript

maxSum = Math.max(maxSum, currentSum);

When to Use This Pattern

When asked to find the highest sum path in a tree that can start and end anywhere, use the maximum path sum pattern with recursion and global tracking.

Common Mistakes

Mistake: Returning the sum of left and right children without ignoring negative sums
Fix: Use Math.max(childSum, 0) to ignore negative paths that reduce total sum

Mistake: Not updating the global max sum at each node
Fix: Update maxSum with the sum passing through the current node to track max anywhere

Mistake: Returning sum of both children instead of max single path down
Fix: Return node.val + max(leftMax, rightMax) to continue path down one side

Summary

Finds the maximum sum of any path in a binary tree where the path can start and end at any node.

Use when you need the highest sum path in a tree, not limited to root or leaves.

The key is to track max sums including both children at each node and ignore negative paths.