Maximum Path Sum in Binary Tree in DSA Javascript - Deep Dive

Overview - Maximum Path Sum in Binary Tree

What is it?

Maximum Path Sum in a Binary Tree means finding the highest total value you can get by adding up node values along any path in the tree. A path can start and end at any nodes, but it must follow parent-child connections. The path does not have to go through the root. This problem helps us understand how to explore all possible routes in a tree to find the best one.

Why it matters

Without this concept, we wouldn't know how to find the best route or connection in a tree structure, which is important in many real-world problems like network routing, decision making, and data analysis. It helps us find the most valuable or strongest connection in complex systems. Without it, we might miss the best solution hidden deep inside the tree.

Where it fits

Before this, you should understand what binary trees are and how to traverse them using recursion. After this, you can learn about more complex tree problems like diameter of a tree or balanced trees. This topic builds your skills in recursion, tree traversal, and dynamic programming.

Mental Model

Core Idea

The maximum path sum is the highest sum of node values along any connected path in the tree, which may pass through or end at any node.

Think of it like...

Imagine a mountain range where each peak has a height (node value). The maximum path sum is like finding the highest possible hiking trail that can start and end anywhere but must follow connected peaks.

        (Node)
       /      \
  (Left)    (Right)

Each node can contribute its value plus the best path from left or right child.
The maximum path can be:
- Left path + Node + Right path (peak path)
- Node + Left path
- Node + Right path
- Node alone

We track the best sum found anywhere in the tree.

Build-Up - 7 Steps

1

Foundation

Understanding Binary Tree Structure

Concept: Learn what a binary tree is and how nodes connect.

A binary tree is a structure where each node has up to two children: left and right. Each node holds a value. Paths are sequences of connected nodes following parent-child links.

Result

You can visualize and identify nodes and their children in a tree.

Understanding the tree structure is essential because the maximum path sum depends on how nodes connect and how paths can be formed.

2

Foundation

Basic Tree Traversal with Recursion

Concept: Learn how to visit nodes using recursion to explore the tree.

Recursion means a function calls itself to process child nodes. For example, to visit all nodes, you call the function on the left child, then right child, then process the current node.

Result

You can write code that visits every node in the tree.

Recursion is the natural way to explore trees because each subtree is itself a tree, allowing us to break down the problem.

3

Intermediate

Calculating Maximum Path Sum Ending at Node

🤔Before reading on: do you think the maximum path sum at a node includes both children or just one? Commit to your answer.

Concept: At each node, find the best path sum that starts from this node and goes down to one child or none.

For each node, calculate the maximum sum of paths starting at this node and going down either left or right child. If a child's path sum is negative, ignore it (use zero). This gives the best single-side path sum.

Result

You get the maximum sum of a path that starts at the current node and extends downward.

Knowing the best downward path at each node helps build solutions for bigger paths that may include both children.

4

Intermediate

Tracking Maximum Path Through Node

🤔Before reading on: do you think the maximum path sum can include both left and right children at the same node? Commit to your answer.

Concept: At each node, consider the path that goes through the node and both children to find a peak path sum.

Calculate the sum of the node's value plus the maximum path sums from left and right children (only if positive). This sum represents a path passing through the node connecting left and right subtrees.

Result

You find the maximum path sum that uses the current node as the highest point.

This step reveals that the maximum path can be a 'peak' including both sides, not just a single branch.

5

Intermediate

Updating Global Maximum Path Sum

🤔Before reading on: do you think the maximum path sum is always at the root or can it be anywhere? Commit to your answer.

Concept: Keep track of the highest path sum found anywhere in the tree during traversal.

Use a global variable to store the maximum path sum found so far. At each node, update this variable if the current peak path sum is higher. This ensures the final answer is the best anywhere.

Result

You have a running record of the best path sum found in the entire tree.

Tracking a global maximum allows the algorithm to find the best path regardless of where it is in the tree.

6

Advanced

Implementing Maximum Path Sum in JavaScript

🤔Before reading on: do you think the recursive function should return the maximum path sum including both children or just one side? Commit to your answer.

Concept: Write a recursive function that returns the best single-side path sum and updates the global maximum for peak paths.

function maxPathSum(root) { let maxSum = -Infinity; function helper(node) { if (!node) return 0; const left = Math.max(helper(node.left), 0); const right = Math.max(helper(node.right), 0); const currentSum = node.val + left + right; maxSum = Math.max(maxSum, currentSum); return node.val + Math.max(left, right); } helper(root); return maxSum; } // Example tree: // 1 // / \ // 2 3 // max path sum = 2 + 1 + 3 = 6

Result

Calling maxPathSum on the example tree returns 6.

Returning only one side's max path sum while updating global max with both sides allows correct calculation of all path types.

7

Expert

Handling Negative Values and Edge Cases

🤔Before reading on: do you think negative node values can increase the maximum path sum? Commit to your answer.

Concept: Understand how negative values affect path sums and how to handle trees with all negative nodes.

Since negative values reduce sums, we ignore negative child paths by using Math.max(childSum, 0). If all nodes are negative, the maximum path sum is the largest single node value. The algorithm naturally handles this by comparing sums with -Infinity initial max.

Result

The algorithm correctly returns the maximum path sum even if all values are negative.

Ignoring negative paths prevents lowering the sum, and initializing maxSum to -Infinity ensures correct results for all-negative trees.

Under the Hood

The algorithm uses recursion to explore every node. At each node, it calculates the maximum path sum starting from that node going down one side. It also considers the path passing through the node connecting left and right children. A global variable tracks the highest sum found. The recursion returns the best single-side path sum to parent calls, enabling building larger paths.

Why designed this way?

This design avoids checking all possible paths explicitly, which would be very slow. Instead, it uses a bottom-up approach where each node's best paths are computed once and reused. Ignoring negative sums simplifies the logic and improves performance. This approach balances clarity, efficiency, and correctness.

          [Node]
          /    \
    [Left]    [Right]
      |          |
  maxLeftSum  maxRightSum
      \          /
       \        /
      maxPathThroughNode
          |
    Update global maxSum
          |
    Return max(node.val + max(left,right), node.val)

Myth Busters - 4 Common Misconceptions

Quick: Does the maximum path sum always include the root node? Commit to yes or no.

Common Belief: The maximum path sum must include the root node because it's the starting point.

Reality: The maximum path sum can be anywhere in the tree and does not have to include the root.

Why it matters: Assuming the root must be included can cause missing the true maximum path deep in a subtree.

Quick: Can negative node values increase the maximum path sum? Commit to yes or no.

Common Belief: Including negative values can sometimes increase the total path sum.

Reality: Negative values always reduce the sum, so they are ignored when calculating maximum path sums.

Why it matters: Including negative paths lowers the sum and leads to incorrect results.

Quick: Is the maximum path sum always a path from root to leaf? Commit to yes or no.

Common Belief: The maximum path sum must be a path from the root down to a leaf node.

Reality: The maximum path sum can start and end at any nodes, not necessarily root or leaf.

Why it matters: Limiting paths to root-to-leaf misses many possible higher sums.

Quick: Does the recursive function return the maximum path sum for the entire tree? Commit to yes or no.

Common Belief: The recursive function returns the maximum path sum for the whole tree at each call.

Reality: The recursive function returns the maximum single-side path sum from the current node, while the global max tracks the overall maximum path sum.

Why it matters: Confusing return values leads to incorrect implementation and wrong answers.

Expert Zone

1

The global maximum path sum can be updated at any node, not just leaves or root, which means the algorithm must check all nodes carefully.

2

Returning only one side's max path sum to the parent avoids counting paths that branch in two directions, which would break the path definition.

3

Initializing the global max to -Infinity ensures correctness even when all node values are negative, a subtle but critical detail.

When NOT to use

This approach is not suitable if the path definition changes, such as allowing cycles or revisiting nodes. For graphs or trees with cycles, use graph algorithms like DFS with visited sets. Also, if you need the actual path nodes, additional tracking is required.

Production Patterns

In production, this pattern is used in network reliability to find strongest connection paths, in game AI for scoring best moves, and in financial models to find optimal investment paths. It is often combined with memoization or iterative traversal for performance.

Connections

Dynamic Programming

Builds-on

Maximum path sum uses overlapping subproblems and optimal substructure, key ideas in dynamic programming, to efficiently compute results.

Graph Theory

Related domain

A binary tree is a special kind of graph; understanding path sums in trees helps grasp path problems in general graphs.

Project Management Critical Path

Analogous concept

Finding the maximum path sum is like identifying the critical path in project management, the longest sequence of dependent tasks determining project duration.

Common Pitfalls

#1 Including negative child path sums in calculations.

Wrong approach:

const left = helper(node.left);
const right = helper(node.right);
const currentSum = node.val + left + right;

Correct approach:

const left = Math.max(helper(node.left), 0);
const right = Math.max(helper(node.right), 0);
const currentSum = node.val + left + right;

Root cause:

Not ignoring negative sums causes the total to decrease, leading to wrong maximum path sums.

#2 Returning the sum including both children to the parent call.

Wrong approach:

return node.val + left + right; // wrong: path can't branch both ways upwards

Correct approach:

return node.val + Math.max(left, right); // correct: path continues only one side

Root cause:

Paths must be linear; returning both sides breaks path definition and inflates sums.

#3 Initializing the global max sum to zero.

Wrong approach:

let maxSum = 0;

Correct approach:

let maxSum = -Infinity;

Root cause:

If all node values are negative, zero initialization falsely reports zero as max sum.

Key Takeaways

Maximum path sum finds the highest sum of connected nodes along any path in a binary tree.

Recursion with careful tracking of single-side path sums and global maximum allows efficient calculation.

Ignoring negative child sums prevents lowering the total and ensures correct results.

The maximum path can be anywhere in the tree, not necessarily including the root or leaves.

Proper initialization and return values are critical to handle all cases, including negative values.

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)