Maximum Path Sum in Binary Tree in DSA Typescript - Execution Trace

Concept Flow - Maximum Path Sum in Binary Tree

Start at root node

↓

Calculate max path sum from left subtree

↓

Calculate max path sum from right subtree

↓

Calculate max path through current node

↓

Update global max if current path sum is higher

↓

Return max path sum including current node and one subtree

↓

Repeat for all nodes

↓

Final global max is the answer

Start from root, recursively find max path sums from left and right children, update global max with path through current node, return max path including one child to parent.

Execution Sample

DSA Typescript

function maxPathSum(root: TreeNode): 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;
}

Recursively computes max path sum in binary tree, updating global max sum at each node.

Execution Table

Step	Operation	Node Visited	Left Max	Right Max	Current Path Sum	Global Max	Return Value	Visual State
1	Visit node	1	0	0	1 + 0 + 0 = 1	1	1 + max(0,0) = 1	1
2	Visit node	2	0	0	2 + 0 + 0 = 2	2	2 + max(0,0) = 2	1 -> 2
3	Back to node	1	2	0	1 + 2 + 0 = 3	3	1 + max(2,0) = 3	1 -> 2
4	Visit node	3	0	0	-3 + 0 + 0 = -3	3	-3 + max(0,0) = 0	1 -> 2, 3
5	Back to node	1	2	0	1 + 2 + 0 = 3	3	3	1 -> 2, 3
6	Final	root	-	-	-	3	-	Final max path sum = 3

💡 All nodes visited, global max updated to 3

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
maxSum	-Infinity	1	2	3	3	3	3
left	-	0	0	2	0	2	-
right	-	0	0	0	0	0	-
return value	-	1	2	3	0	3	-

Key Moments - 3 Insights

Why do we use Math.max(dfs(node.left), 0) instead of just dfs(node.left)?

Because negative path sums reduce the total, we ignore them by taking max with 0. See execution_table rows 2 and 4 where left or right max is 0 instead of negative.

Why do we update global max with node.val + left + right instead of just one side?

Because the max path can pass through the current node connecting left and right subtrees. This is shown in execution_table row 3 where current path sum includes both left and right.

Why does the dfs function return node.val + max(left, right) and not include both sides?

Because when returning to parent, path must be linear (one branch). Including both sides would create a fork, which is not allowed in path definition. See return values in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the global max value?

A 1

B 3

C 4

D 2

💡 Hint

Check the 'Global Max' column at Step 3 in execution_table

At which step does the algorithm ignore a negative path sum by using 0 instead?

A Step 4

B Step 2

C Step 1

D Step 5

💡 Hint

Look at 'Left Max' and 'Right Max' columns for negative values replaced by 0 in execution_table

If the node value at step 4 was positive instead of -3, how would the global max change?

A It would stay the same

B It would decrease

C It would increase

D It would become zero

💡 Hint

Consider how global max updates with current path sum in execution_table rows

Concept Snapshot

Maximum Path Sum in Binary Tree:
- Use DFS to explore each node
- Calculate max path sum from left and right children, ignore negatives
- Update global max with node.val + left + right
- Return node.val + max(left, right) to parent
- Final global max is the answer

Full Transcript

This visualization shows how to find the maximum path sum in a binary tree. We start at the root and recursively calculate the maximum path sums from the left and right children. Negative sums are ignored by taking the maximum with zero. At each node, we calculate the path sum that passes through it by adding its value and the maximum sums from both children. We update a global maximum if this sum is higher than before. When returning to the parent, we only include the node's value plus the larger of the two child sums to keep the path linear. The final global maximum after visiting all nodes is the maximum path sum in the tree.

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