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.

Practice

1. What does the "Maximum Path Sum in Binary Tree" problem ask you to find?

easy

A. The sum of all node values in the tree

B. The longest path length in the binary tree

C. The highest sum of values along any path between two nodes in the tree

D. The maximum value of a single node in the tree

Solution

1. Step 1: Understand the problem definition

   The problem asks for the maximum sum of node values along any path in the binary tree. A path can start and end at any nodes, but must be connected.

2. Step 2: Differentiate from other path problems

   This is not about longest path length or total sum of all nodes, but the maximum sum of values on any path.

3. Final Answer:

   The highest sum of values along any path between two nodes in the tree -> Option C

4. Quick Check:

   Maximum path sum = highest sum path [OK]

Hint: Focus on sum of connected nodes, not length or single node [OK]

Common Mistakes:

• Confusing maximum path sum with longest path length
• Thinking path must start at root
• Summing all nodes instead of a path

2. Which of the following is the correct base case return value for a recursive function computing maximum path sum in a binary tree node when the node is null?

easy

A. -Infinity

B. 1

C. null

D. 0

Solution

1. Step 1: Consider the meaning of base case for null node

   When the node is null, the maximum gain from this subtree is 0 (choose not to extend path here).

2. Step 2: Why not others?

   -Infinity works only with Math.max(0, result) but 0 is standard and cleaner. Returning 0 allows proper clamping in parent. null or 1 cause type/math errors.

3. Final Answer:

   0 -> Option D

4. Quick Check:

   Base case for null = 0 [OK]

Hint: Return 0 for null to represent zero contribution [OK]

Common Mistakes:

• Returning -Infinity without Math.max(0, ·)
• Returning null causing type errors
• Returning positive values skewing max

3. What is the output of the following code snippet for maximum path sum?

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

function maxPathSum(root) {
  let maxSum = -Infinity;
  function dfs(node) {
    if (!node) return 0;
    let left = Math.max(dfs(node.left), 0);
    let right = Math.max(dfs(node.right), 0);
    maxSum = Math.max(maxSum, node.val + left + right);
    return node.val + Math.max(left, right);
  }
  dfs(root);
  return maxSum;
}

const root = new TreeNode(-10, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
console.log(maxPathSum(root));

medium

A. 42

B. 35

C. 27

D. 20

Solution

1. Step 1: Trace dfs on left subtree

   Left child 9: left=0, right=0, maxSum = 9, returns 9.

2. Step 2: Trace dfs on right subtree

   dfs(15)=15 updates maxSum=15; dfs(7)=7 keeps 15; at 20: left=15, right=7, maxSum = max(15, 20+15+7=42)=42, returns 20+15=35.

3. Step 3: Calculate root node max sum

   Root: left=9, right=35, path sum -10+9+35=34 <42, maxSum remains 42.

4. Final Answer:

   42 -> Option A

5. Quick Check:

   Max path sum = 42 [OK]

Hint: Add node + max(left, right) and update maxSum with both sides [OK]

Common Mistakes:

• Not ignoring negative sums by using Math.max with 0
• Adding left and right children incorrectly
• Confusing return value with maxSum update

4. Identify the bug in this maximum path sum function and select the fix:

function maxPathSum(root) {
  let maxSum = -Infinity;
  function dfs(node) {
    if (!node) return -Infinity;
    let left = dfs(node.left);
    let right = dfs(node.right);
    maxSum = Math.max(maxSum, node.val + left + right);
    return node.val + Math.max(left, right);
  }
  dfs(root);
  return maxSum;
}

medium

A. Add check to ignore negative sums with Math.max(left, 0)

B. Change base case return from -Infinity to 0

C. Initialize maxSum to 0 instead of -Infinity

D. Return maxSum inside dfs instead of outside

Solution

1. Step 1: Analyze base case and recursive calls

   Returning -Infinity for null nodes causes left and right to be -Infinity, which breaks addition and max calculations.

2. Step 2: Fix by ignoring negative sums

   Use Math.max(dfs(node.left), 0) and Math.max(dfs(node.right), 0) to ignore negative paths and avoid incorrect sums.

3. Final Answer:

   Add check to ignore negative sums with Math.max(left, 0) -> Option A

4. Quick Check:

   Ignore negative sums with Math.max(..., 0) [OK]

Hint: Ignore negative child sums by max with 0 to fix bugs [OK]

Common Mistakes:

• Returning -Infinity breaks addition
• Not ignoring negative sums from children
• Changing maxSum initialization wrongly

5. Given a binary tree where some nodes have negative values, how would you modify the maximum path sum algorithm to handle the case where all values are negative?

hard

A. Allow paths to be empty and return 0 if all sums are negative

B. Track the maximum single node value separately and compare with path sums

C. Use Math.max with 0 on child sums to ignore negatives

D. Initialize maxSum to -Infinity and do not ignore negative child sums

Solution

1. Step 1: Understand all-negative case

   The max path sum is the highest (least negative) single node value. Paths must include at least one node.

2. Step 2: Key modification

   Tracking the maximum single node value separately ensures that if all child sums are negative, the algorithm still returns the maximum node value. Using Math.max(0, dfs(child)) ignores negative child sums but can miss the max single node if all are negative.

3. Final Answer:

   Track the maximum single node value separately and compare with path sums -> Option B

4. Quick Check:

   Separate max node tracking handles all-negative correctly [OK]

Hint: Track max single node separately to handle all-negative cases [OK]

Common Mistakes:

• Allowing empty path return 0 (invalid)
• Not tracking max node separately (misses max negative node)
• Not ignoring negative child sums (misses single nodes)