DP on Trees Maximum Path Sum in DSA Javascript

Mental Model

We find the biggest sum of values along any path in a tree by checking each node's best path through its children.

Analogy: Imagine climbing a mountain with many branches. At each fork, you choose the best path that gives you the most reward, and you keep track of the best total reward you can get anywhere on the mountain.

      1
     / \
    2   3
   / \   \
  4   5   6

Each number is a node value. We want the path with the biggest sum.

Dry Run Walkthrough

Input: Tree: 1 -> 2 -> 4, 2 -> 5, 1 -> 3 -> 6 with values [1, 2, 3, 4, 5, 6]

Goal: Find the maximum sum of any path in the tree, which can start and end at any nodes.

Step 1: Start DFS at node 4 (leaf), max path sum from 4 is 4

4 (max path sum = 4)

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

Step 2: Start DFS at node 5 (leaf), max path sum from 5 is 5

5 (max path sum = 5)

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

Step 3: At node 2, calculate max path sum including children: max(4,5) + 2 = 7; update global max with 4 + 2 + 5 = 11

2 -> 4 (4), 2 -> 5 (5), max path sum at 2 = 7, global max = 11

Why: We consider paths through node 2 connecting both children for max sum

Step 4: Start DFS at node 6 (leaf), max path sum from 6 is 6

6 (max path sum = 6)

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

Step 5: At node 3, max path sum including child 6 is 3 + 6 = 9; update global max if needed

3 -> 6 (6), max path sum at 3 = 9, global max = 11

Why: Only one child, so max path sum is node + child's max

Step 6: At root node 1, max path sum including children: max(7,9) + 1 = 10; update global max with 7 + 1 + 9 = 17

1 -> 2 (7), 1 -> 3 (9), max path sum at 1 = 10, global max = 17

Why: Check if path through root connecting both children is bigger

Result:

Maximum path sum is 17, path is 5 -> 2 -> 1 -> 3 -> 6

Annotated Code

DSA Javascript

class TreeNode {
  constructor(val) {
    this.val = val;
    this.children = [];
  }
}

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

  function dfs(node) {
    if (!node) return 0;

    let maxChildSums = [];
    for (const child of node.children) {
      const childSum = dfs(child);
      maxChildSums.push(childSum);
    }

    // Take top two max sums from children or 0 if negative
    maxChildSums = maxChildSums.map(x => Math.max(x, 0));
    maxChildSums.sort((a, b) => b - a);

    // Update global max: node + top two children sums
    const currentMax = node.val + (maxChildSums[0] || 0) + (maxChildSums[1] || 0);
    if (currentMax > maxSum) maxSum = currentMax;

    // Return max path sum including node and one child
    return node.val + (maxChildSums[0] || 0);
  }

  dfs(root);
  return maxSum;
}

// Build tree from example
const root = new TreeNode(1);
const node2 = new TreeNode(2);
const node3 = new TreeNode(3);
const node4 = new TreeNode(4);
const node5 = new TreeNode(5);
const node6 = new TreeNode(6);

root.children.push(node2, node3);
node2.children.push(node4, node5);
node3.children.push(node6);

console.log(maxPathSum(root));

for (const child of node.children) { const childSum = dfs(child); maxChildSums.push(childSum); }

recursively get max path sums from all children

maxChildSums = maxChildSums.map(x => Math.max(x, 0)); maxChildSums.sort((a, b) => b - a);

ignore negative sums and sort to find top two max child sums

const currentMax = node.val + (maxChildSums[0] || 0) + (maxChildSums[1] || 0); if (currentMax > maxSum) maxSum = currentMax;

update global max with sum through node and two best children

return node.val + (maxChildSums[0] || 0);

return max path sum including node and one child for parent's use

Output

17

Complexity Analysis

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

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

vs Alternative: Naive approach checking all paths is O(n^2) or worse; DP on trees reduces to O(n)

Edge Cases

Empty tree (root is null)

Returns 0 meaning no path

DSA Javascript

if (!node) return 0;

Tree with all negative values

Returns the maximum single node value as path sum ignoring negative children

DSA Javascript

maxChildSums = maxChildSums.map(x => Math.max(x, 0));

Tree with single node

Returns the value of the single node

DSA Javascript

if (!node) return 0;

When to Use This Pattern

When asked for the maximum sum path in a tree that can start and end anywhere, use DP on trees by combining child results and tracking global max.

Common Mistakes

Mistake: Returning sum of all children instead of only the best one or two
Fix: Only consider the top two maximum child sums to form paths through the current node

Mistake: Not ignoring negative child sums, which lowers the total
Fix: Use Math.max(childSum, 0) to ignore negative sums

Mistake: Updating global max only with single child paths, missing paths through node connecting two children
Fix: Update global max with node.val + top two child sums

Summary

Finds the maximum sum of any path in a tree by combining best child paths at each node.

Use when you need the highest sum path that can start and end anywhere in a tree.

The key is to track the best one-child path for recursion and the best two-child path for global max.

Practice

1. What does the "maximum path sum" in a binary tree represent?
Maximum path sum means:

easy

A. The largest sum of node values along any path in the tree

B. The number of nodes in the longest path

C. The smallest sum of node values along any path

D. The sum of all node values in the tree

Solution

1. Step 1: Understand the path definition

   A path in a tree is any sequence of nodes connected by edges, not necessarily starting at the root.

2. Step 2: Define maximum path sum meaning

   The maximum path sum is the highest total value you get by adding node values along any such path.

3. Final Answer:

   The largest sum of node values along any path in the tree -> Option A

4. Quick Check:

   Maximum path sum = largest node value sum [OK]

Hint: Maximum path sum is about node values, not count or minimum [OK]

Common Mistakes:

• Confusing path length with sum
• Thinking path must start at root
• Choosing sum of all nodes instead of max path

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

function maxPathSum(node) {
  if (___) return 0;
  // rest of code
}

easy

A. node.value === 0

B. node.left === null && node.right === null

C. node === null

D. node === undefined

Solution

1. Step 1: Identify when recursion should stop

   When the node is empty (null), there is no path, so return 0.

2. Step 2: Check options for base case

   Only checking if node is null correctly handles leaf children and empty trees.

3. Final Answer:

   node === null -> Option C

4. Quick Check:

   Base case: node null means no path [OK]

Hint: Base case is node === null to stop recursion [OK]

Common Mistakes:

• Using node.value === 0 which is incorrect
• Checking both children null instead of node null
• Using node === undefined which is less common

3. What is the output of the following code snippet?

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 === null) 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 tree = new TreeNode(1, new TreeNode(2), new TreeNode(3));
console.log(maxPathSum(tree));

medium

A. 6

B. 5

C. 3

D. 1

Solution

1. Step 1: Calculate max path sums for each node

   For leaf nodes 2 and 3, max path sum is their value (2 and 3). For root 1, left=2, right=3, sum=1+2+3=6.

2. Step 2: Update maxSum and return correct values

   maxSum updates to 6 at root. Return values propagate correctly.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Sum of 1+2+3 = 6 [OK]

Hint: Add node + max left + max right, ignore negatives [OK]

Common Mistakes:

• Forgetting to ignore negative sums
• Returning node.val + left + right instead of max(left, right)
• Confusing maxSum update with return value

4. Find the bug in this code for maximum path sum in a binary tree:

function maxPathSum(root) {
  let maxSum = -Infinity;
  function dfs(node) {
    if (!node) return 0;
    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. It returns maxSum before dfs call

B. It does not ignore negative sums from children

C. It uses wrong base case condition

D. It adds node.val twice in maxSum

Solution

1. Step 1: Check handling of negative child sums

   The code uses left = dfs(node.left) directly without ignoring negatives, which can reduce maxSum incorrectly.

2. Step 2: Correct approach to ignore negatives

   Should use left = Math.max(dfs(node.left), 0) and similarly for right to avoid negative paths.

3. Final Answer:

   It does not ignore negative sums from children -> Option B

4. Quick Check:

   Ignore negatives to maximize path sum [OK]

Hint: Use Math.max(childSum, 0) to skip negative paths [OK]

Common Mistakes:

• Not ignoring negative sums
• Returning before dfs call
• Wrong base case check

5. Given a binary tree where nodes can have negative values, how would you modify the maximum path sum algorithm to handle the case where all node values are negative?
Choose the best approach:

hard

A. Initialize maxSum to 0 and ignore negative sums

B. Only consider paths starting at the root

C. Return 0 if all nodes are negative

D. Initialize maxSum to -Infinity and allow paths with negative sums

Solution

1. Step 1: Understand negative values impact

   If all nodes are negative, ignoring negative sums by replacing with 0 would incorrectly return 0 instead of the max negative value.

2. Step 2: Use -Infinity initialization and allow negative sums

   Initialize maxSum to -Infinity and do not ignore negative sums completely, so the max negative node is chosen.

3. Final Answer:

   Initialize maxSum to -Infinity and allow paths with negative sums -> Option D

4. Quick Check:

   Allow negative sums to handle all-negative nodes [OK]

Hint: Use -Infinity start and allow negatives for all-negative trees [OK]

Common Mistakes:

• Ignoring negatives leads to wrong zero result
• Returning 0 when no positive path exists
• Restricting paths to root only