DP on Trees Maximum Path Sum in DSA Typescript

Mental Model

We want to find the biggest sum of values along any path in a tree, where a path can start and end at any nodes. We use a method that remembers best sums from children to avoid repeating work.

Analogy: Imagine a tree of roads with tolls on each road. We want to find the most profitable route that can start and end anywhere, but we calculate profits from bottom roads up to avoid checking every route again and again.

      1
     / \
    2   3
   / \   \
  4   5   6
Each node has a value. We want the max sum path anywhere in this tree.

Dry Run Walkthrough

Input: Tree: Node values = {1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6}, edges: 1-2, 1-3, 2-4, 2-5, 3-6

Goal: Find the maximum sum of values along any path in the tree.

Step 1: Start DFS at node 1, explore left child node 2

Visiting node 1 -> going to node 2

Why: We need to explore children to find max sums from bottom up

Step 2: At node 2, explore left child node 4

Visiting node 2 -> going to node 4

Why: Calculate max path sums from children before using node 2

Step 3: At node 4, no children, max path down = 4, update global max = 4

Node 4 max down = 4, global max = 4

Why: Leaf node max path is its own value

Step 4: Back to node 2, explore right child node 5

Visiting node 2 -> going to node 5

Why: Need max sums from both children to consider paths through node 2

Step 5: At node 5, no children, max path down = 5, update global max = 5

Node 5 max down = 5, global max = 5

Why: Leaf node max path is its own value

Step 6: At node 2, calculate max path down = max(4,5) + 2 = 7; max path through node 2 = 4 + 2 + 5 = 11; update global max = 11

Node 2 max down = 7, global max = 11

Why: Max path can go through node 2 connecting both children

Step 7: Back to node 1, explore right child node 3

Visiting node 1 -> going to node 3

Why: Explore other subtree to find max path

Step 8: At node 3, explore right child node 6

Visiting node 3 -> going to node 6

Why: Calculate max sums from children

Step 9: At node 6, no children, max path down = 6, update global max = 11 (unchanged)

Node 6 max down = 6, global max = 11

Why: Leaf node max path is its own value

Step 10: At node 3, max path down = max(0,6) + 3 = 9; max path through node 3 = 3 + 6 = 9; update global max = 11 (unchanged)

Node 3 max down = 9, global max = 11

Why: Max path through node 3 is less than current global max

Step 11: At node 1, max path down = max(7,9) + 1 = 10; max path through node 1 = 7 + 1 + 9 = 17; update global max = 17

Node 1 max down = 10, global max = 17

Why: Max path through root connects left and right subtrees

Result:

Final max path sum = 17
Path example: 4 -> 2 -> 1 -> 3 -> 6

Annotated Code

DSA Typescript

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

function maxPathSum(root: TreeNode | null): number {
  let maxSum = -Infinity;

  function dfs(node: TreeNode | null): number {
    if (!node) return 0;

    // Store max path sums from children
    let maxChildSums: number[] = [];
    for (const child of node.children) {
      const childSum = dfs(child);
      maxChildSums.push(childSum);
    }

    // If no children, max down path is node.val
    if (maxChildSums.length === 0) {
      maxSum = Math.max(maxSum, node.val);
      return node.val;
    }

    // Sort child sums descending to pick top two
    maxChildSums.sort((a, b) => b - a);

    // Max path down from this node is node.val + max child sum if positive
    const maxDown = node.val + Math.max(0, maxChildSums[0]);

    // Max path through this node can include top two child sums if positive
    const topTwoSum = node.val +
      (maxChildSums[0] > 0 ? maxChildSums[0] : 0) +
      (maxChildSums.length > 1 && maxChildSums[1] > 0 ? maxChildSums[1] : 0);

    maxSum = Math.max(maxSum, topTwoSum);

    return maxDown;
  }

  dfs(root);
  return maxSum;
}

// Driver code to build tree and test
const nodes: {[key: number]: TreeNode} = {};
for (let i = 1; i <= 6; i++) {
  nodes[i] = new TreeNode(i);
}
// Build tree edges
nodes[1].children.push(nodes[2], nodes[3]);
nodes[2].children.push(nodes[4], nodes[5]);
nodes[3].children.push(nodes[6]);

console.log(maxPathSum(nodes[1]));

if (!node) return 0;

stop recursion at null nodes

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

collect max path sums from all children

if (maxChildSums.length === 0) { maxSum = Math.max(maxSum, node.val); return node.val; }

leaf node max path is its own value

maxChildSums.sort((a, b) => b - a);

sort child sums descending to pick top two

const maxDown = node.val + Math.max(0, maxChildSums[0]);

max path down includes node plus best child if positive

const topTwoSum = node.val + (maxChildSums[0] > 0 ? maxChildSums[0] : 0) + (maxChildSums.length > 1 && maxChildSums[1] > 0 ? maxChildSums[1] : 0);

max path through node includes node plus top two children if positive

maxSum = Math.max(maxSum, topTwoSum);

update global max path sum

return maxDown;

return max path down for parent's calculation

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 linear time

Edge Cases

Empty tree (root is null)

Returns -Infinity or no path sum; handled by base case returning 0

DSA Typescript

if (!node) return 0;

Single node tree

Returns the node's value as max path sum

DSA Typescript

if (maxChildSums.length === 0) { maxSum = Math.max(maxSum, node.val); return node.val; }

All negative values

Returns the maximum single node value (least negative)

DSA Typescript

maxSum initialized to -Infinity and updated with Math.max

When to Use This Pattern

When asked to find max sum path in a tree that can start and end anywhere, use DP on trees by computing max path sums from children and combining them at each node.

Common Mistakes

Mistake: Returning sum of all children instead of max path down from one child
Fix: Only consider the maximum child path sum for max down path, not sum of all children

Mistake: Not handling negative child sums by including them
Fix: Use Math.max(0, childSum) to ignore negative sums

Mistake: Not updating global max with path through node combining two children
Fix: Update global max with sum of node value plus top two child sums if positive

Summary

Finds the maximum sum of values along any path in a tree using bottom-up DP.

Use when you need max path sums in trees where paths can start and end anywhere.

Remember to combine max sums from up to two children at each node and track global max.

Practice

1. What does the "maximum path sum" in a tree represent in the context of dynamic programming on trees?

easy

A. The sum of all node values in the tree

B. The largest sum of node values along any path between two nodes in the tree

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

D. The longest path length in the tree

Solution

1. Step 1: Understand the problem definition

   The maximum path sum is about finding the path between any two nodes that yields the highest sum of node values.

2. Step 2: Differentiate from other sums

   It is not the sum of all nodes or just the max node value, but the max sum along a connected path.

3. Final Answer:

   The largest sum of node values along any path between two nodes in the tree -> Option B

4. Quick Check:

   Maximum path sum = max sum on any path [OK]

Hint: Maximum path sum is about any path, not whole tree sum [OK]

Common Mistakes:

• Confusing maximum path sum with sum of all nodes
• Thinking it is just the max node value
• Assuming path must start at root

2. Which of the following TypeScript function signatures correctly represents a recursive function to find maximum path sum in a binary tree node?

easy

A. function maxPathSum(node: TreeNode): void

B. function maxPathSum(node: number): number

C. function maxPathSum(): number

D. function maxPathSum(node: TreeNode | null): number

Solution

1. Step 1: Check parameter type

   The function must accept a TreeNode or null to handle empty nodes.

2. Step 2: Check return type

   It should return a number representing the max path sum from that node.

3. Final Answer:

   function maxPathSum(node: TreeNode | null): number -> Option D

4. Quick Check:

   Correct parameter and return type [OK]

Hint: Function must accept node or null and return number [OK]

Common Mistakes:

• Using wrong parameter type (e.g., number instead of TreeNode)
• Returning void instead of number
• Not allowing null for leaf children

3. Consider the following TypeScript code snippet for maximum path sum in a binary tree:

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

function maxPathSum(root: TreeNode | null): number {
  let maxSum = -Infinity;
  function dfs(node: TreeNode | null): number {
    if (!node) return 0;
    const left = Math.max(dfs(node.left), 0);
    const 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));

What is the output of this code?

medium

A. 3

B. 5

C. 6

D. 1

Solution

1. Step 1: Trace DFS on tree nodes

   For node 2 and 3, max path sums are 2 and 3 respectively. For root 1, left=2, right=3.

2. Step 2: Calculate maxSum updates

   maxSum updates to max(-Infinity, 1+2+3) = 6. Return value for root is 1 + max(2,3) = 4 but maxSum remains 6.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   Sum of path 2->1->3 = 6 [OK]

Hint: Sum left + node + right for max path sum [OK]

Common Mistakes:

• Returning max path from root only, ignoring subtrees
• Not using Math.max with 0 to ignore negative sums
• Confusing return value with maxSum global

4. The following TypeScript code attempts to find the maximum path sum in a binary tree but has a bug:

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

What is the bug in this code?

medium

A. It does not ignore negative sums from left or right subtree

B. It returns void instead of number

C. It does not handle null root

D. It uses global variable incorrectly

Solution

1. Step 1: Analyze subtree sums usage

   The code uses left and right sums directly without ignoring negative values.

2. Step 2: Identify impact on maxSum

   Negative sums can reduce maxSum, so we must use Math.max(dfs(...), 0) to ignore negatives.

3. Final Answer:

   It does not ignore negative sums from left or right subtree -> Option A

4. Quick Check:

   Negative subtree sums must be ignored [OK]

Hint: Use Math.max(dfs(...), 0) to ignore negatives [OK]

Common Mistakes:

• Not checking for negative subtree sums
• Assuming dfs returns void
• Ignoring null root case

5. Given a binary tree where some nodes have negative values, how would you modify the dynamic programming approach to find the maximum path sum that can start and end at any node, but the path must go downwards (only from parent to child)?

hard

A. Use DFS to compute max downward path sum at each node ignoring negative sums by max(0, childSum)

B. Use BFS to find the longest path ignoring node values

C. Sum all node values and subtract minimum node value

D. Only consider paths that include the root node

Solution

1. Step 1: Understand downward path constraint

   The path must go downwards from parent to child, so use DFS to explore children.

2. Step 2: Handle negative values

   Ignore negative sums by taking max(0, childSum) to avoid reducing path sum.

3. Step 3: Calculate max path sum

   At each node, max downward path sum = node.val + max(leftChildSum, rightChildSum, 0).

4. Final Answer:

   Use DFS to compute max downward path sum at each node ignoring negative sums by max(0, childSum) -> Option A

5. Quick Check:

   Downward path + ignore negatives = DFS with max(0, childSum) [OK]

Hint: Downward path max sum uses DFS and max(0, childSum) [OK]

Common Mistakes:

• Using BFS instead of DFS
• Ignoring negative values incorrectly
• Forcing path through root only