Maximum Path Sum in Binary Tree in DSA Typescript

Mental Model

Find the highest sum you can get by traveling along any path in the tree, where a path can start and end at any node.

Analogy: Imagine a mountain range where each peak has a height (value). You want to find the highest possible trail that can go up and down connecting peaks, but you cannot jump around; you must walk along connected peaks.

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

Dry Run Walkthrough

Input: Binary tree: root=10, left=2, right=10, left.left=20, left.right=1, right.right=-25, right.right.left=3, right.right.right=4

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

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

20 (leaf) -> max path sum = 20

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

Step 2: At node 1 (leaf), max path sum is 1

1 (leaf) -> max path sum = 1

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

Step 3: At node 2, calculate max path sum including left and right children: max(20,0)+2+max(1,0)=23; max path sum from node 2 to parent is 2 + max(20,1) = 22

2 -> left=20, right=1 -> max path sum through node 2 = 23, max path sum to parent = 22

Why: We consider max path through node 2 and also max path to parent for further calculation

Step 4: At node 3 (leaf), max path sum is 3

3 (leaf) -> max path sum = 3

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

Step 5: At node 4 (leaf), max path sum is 4

4 (leaf) -> max path sum = 4

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

Step 6: At node -25, calculate max path sum including children: max(3,0)+(-25)+max(4,0) = -18; max path sum to parent is -25 + max(3,4) = -21

-25 -> left=3, right=4 -> max path sum through node -25 = -18, max path sum to parent = -21

Why: Negative node reduces sum, but we still consider max path to parent

Step 7: At node 10 (right child of root), max path sum to parent is 10 + max(0, -21) = 10; max path sum through node is 10

10 (right child) -> max path sum to parent = 10, max path sum through node = 10

Why: Right child has no left child, and right child's right subtree max path sum to parent is negative, so ignored

Step 8: At root 10, calculate max path sum including left and right children: max(22,0)+10+max(10,0) = 42; max path sum to parent is 10 + max(22,10) = 32

root 10 -> left=22, right=10 -> max path sum through root = 42, max path sum to parent = 32

Why: Root combines best paths from left and right to find max path sum in entire tree

Result:

Maximum path sum in tree = 42
Final max path: 20 -> 2 -> 10 -> 10

Annotated Code

DSA Typescript

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

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

  function helper(node: TreeNode | null): number {
    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); // ignore negative sums

    // 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 path sum including current node and one subtree to parent
    return node.val + Math.max(leftMax, rightMax);
  }

  helper(root);
  return maxSum;
}

// Driver code to build tree and test
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 including current node and one subtree to parent

Output

42

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 causing exponential time; this approach uses recursion and pruning negative sums for linear time

Edge Cases

Empty tree (root is null)

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

DSA Typescript

if (node === null) return 0;

Tree with all negative values

Ignores negative child sums but still considers node's own value; returns the least negative node value

DSA Typescript

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

Single node tree

Returns the value of the single node as max path sum

DSA Typescript

if (node === null) return 0;

When to Use This Pattern

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

Common Mistakes

Mistake: Returning sum of both children to parent causing invalid paths
Fix: Return node value plus max of one child's max path sum only

Mistake: Not ignoring negative sums from children, which lowers max path sum
Fix: Use Math.max(childSum, 0) to ignore negative sums

Summary

Finds the highest sum path in a binary tree that can start and end at any node.

Use when you need the maximum sum of connected nodes in any path within a tree.

The key is to track max sums from children ignoring negatives and update a global max including both children.

Practice

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

easy

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

B. The longest path length in the tree

C. The sum of all node values in the tree

D. The minimum value node in the tree

Solution

1. Step 1: Understand the problem goal

   The problem asks for the maximum sum of values along any path in the binary tree, where a path can start and end at any nodes.

2. Step 2: Differentiate from other tree sums

   This is different from longest path or total sum; it focuses on the maximum sum achievable on any path.

3. Final Answer:

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

4. Quick Check:

   Maximum path sum = highest node value sum [OK]

Hint: Focus on sums along paths, not lengths or totals [OK]

Common Mistakes:

• Confusing path sum with longest path length
• Summing all nodes instead of a path
• Looking for minimum instead of maximum

2. Which TypeScript function signature correctly represents a function to find maximum path sum in a binary tree node?

easy

A. function maxPathSum(root: number[]): number

B. function maxPathSum(root: TreeNode | null): number

C. function maxPathSum(root: string): string

D. function maxPathSum(root: TreeNode): void

Solution

1. Step 1: Identify correct parameter type

   The function should accept a binary tree node or null, so TreeNode | null is correct.

2. Step 2: Identify correct return type

   The function returns a number representing the maximum path sum, so return type is number.

3. Final Answer:

   function maxPathSum(root: TreeNode | null): number -> Option B

4. Quick Check:

   Input: TreeNode or null, Output: number [OK]

Hint: Function input is tree node or null, output is number [OK]

Common Mistakes:

• Using array or string instead of TreeNode
• Returning void instead of number
• Not allowing null as input

3. Given the following TypeScript code, what is the output?

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number, 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 helper(node: TreeNode | null): number {
    if (!node) return 0;
    const left = Math.max(helper(node.left), 0);
    const right = Math.max(helper(node.right), 0);
    maxSum = Math.max(maxSum, node.val + left + right);
    return node.val + Math.max(left, right);
  }
  helper(root);
  return maxSum;
}

const tree = new TreeNode(1, new TreeNode(2), new TreeNode(3));
console.log(maxPathSum(tree));

medium

A. 3

B. 5

C. 1

D. 6

Solution

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

   Node 2 and 3 have no children, so max path sums are 2 and 3. For root 1, left=2, right=3, total=1+2+3=6.

2. Step 2: Determine maximum path sum

   Maximum path sum is max of all nodes' sums: max(2,3,6) = 6.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Sum(1+2+3) = 6 [OK]

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

Common Mistakes:

• Ignoring zero floor for negative sums
• Returning sum of only root and one child
• Confusing return value with maxSum variable

4. Identify the bug in this TypeScript function for maximum path sum:

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

medium

A. Returns node.val + min(left, right) instead of max

B. helper function missing base case

C. maxSum initialized to 0 instead of -Infinity

D. Does not call helper on root

Solution

1. Step 1: Check maxSum initialization

   maxSum initialized to 0 can cause wrong result if all node values are negative.

2. Step 2: Correct initialization for negative values

   Initialize maxSum to -Infinity to handle negative node values correctly.

3. Final Answer:

   maxSum initialized to 0 instead of -Infinity -> Option C

4. Quick Check:

   maxSum must start at -Infinity for negative nodes [OK]

Hint: Initialize maxSum to -Infinity to handle negatives [OK]

Common Mistakes:

• Starting maxSum at 0 causes wrong max for negative trees
• Forgetting base case returns 0
• Using min instead of max for return

5. Given a binary tree with nodes: root= -10, left=9, right=20, right.left=15, right.right=7, what is the maximum path sum?

hard

A. 42

B. 35

C. 27

D. 20

Solution

1. Step 1: Calculate max path sums for subtrees

   Right subtree max path: 15 + 20 + 7 = 42. Left subtree max is 9. Root is -10.

2. Step 2: Determine overall max path sum

   Max path sum is max of 42 (right subtree path), 9 (left), and paths including root. The max is 42.

3. Final Answer:

   42 -> Option A

4. Quick Check:

   Sum(15+20+7) = 42 [OK]

Hint: Check all subtree sums including root, pick max [OK]

Common Mistakes:

• Ignoring path through both children and root
• Choosing sum of root and one child only
• Not considering negative root value impact