DP on Trees Maximum Path Sum in DSA Python - Execution Trace

Concept Flow - DP on Trees Maximum Path Sum

Start at root node

↓

Recursively find max path sum from left child

↓

Recursively find max path sum from right child

↓

Calculate max path through current node

↓

Update global max if current path is higher

↓

Return max path sum including current node and one child

↓

Repeat for all nodes

↓

Final max path sum is global max

We start at the root and recursively find max path sums from left and right children. At each node, we calculate the max path passing through it and update a global max. We return the max path including the node and one child to parent.

Execution Sample

DSA Python

def maxPathSum(root):
    max_sum = float('-inf')
    def dfs(node):
        nonlocal max_sum
        if not node:
            return 0
        left = max(dfs(node.left), 0)
        right = max(dfs(node.right), 0)
        max_sum = max(max_sum, node.val + left + right)
        return node.val + max(left, right)
    dfs(root)
    return max_sum

This code finds the maximum path sum in a binary tree by exploring all paths recursively and tracking the highest sum found.

Execution Table

Step	Operation	Node Visited	Left Max	Right Max	Current Max Path	Global Max	Return Value	Visual State
1	Start DFS	Root (1)	-	-	-	-∞	-	Tree: 1 / \ 2 3
2	DFS Left Child	Node 2	-	-	-	-∞	-	Tree: 2 (leaf)
3	DFS Left Child of 2	None	0	0	0	-∞	0	Leaf reached
4	DFS Right Child of 2	None	0	0	0	-∞	0	Leaf reached
5	Calculate at 2	Node 2	0	0	2 + 0 + 0 = 2	2	2	Path: 2
6	Return to 1	Node 1	2	-	-	2	-	Partial path from left: 2
7	DFS Right Child	Node 3	-	-	-	2	-	Tree: 3 / \ 4 5
8	DFS Left Child of 3	Node 4	-	-	-	2	-	Leaf 4
9	DFS Left Child of 4	None	0	0	0	2	0	Leaf reached
10	DFS Right Child of 4	None	0	0	0	2	0	Leaf reached
11	Calculate at 4	Node 4	0	0	4 + 0 + 0 = 4	4	4	Path: 4
12	Return to 3	Node 3	4	-	-	4	-	Partial path from left: 4
13	DFS Right Child of 3	Node 5	-	-	-	4	-	Leaf 5
14	DFS Left Child of 5	None	0	0	0	4	0	Leaf reached
15	DFS Right Child of 5	None	0	0	0	4	0	Leaf reached
16	Calculate at 5	Node 5	0	0	5 + 0 + 0 = 5	5	5	Path: 5
17	Return to 3	Node 3	4	5	-	5	-	Partial path from right: 5
18	Calculate at 3	Node 3	4	5	3 + 4 + 5 = 12	12	8	Path through 3: 12
19	Return to 1	Node 1	2	8	-	12	-	Partial path from right: 8
20	Calculate at 1	Node 1	2	8	1 + 2 + 8 = 11	12	9	Path through 1: 11
21	End DFS	Root (1)	-	-	-	12	-	Max path sum found: 12

💡 DFS completes after visiting all nodes; global max path sum is 12

Variable Tracker

Variable	Start	After Step 5	After Step 11	After Step 16	After Step 18	After Step 20	Final
max_sum	-∞	2	4	5	12	12	12
left	-	0	0	0	4	2	-
right	-	0	0	0	5	8	-
return_value at Node 2	-	2	-	-	-	-	-
return_value at Node 4	-	-	4	-	-	-	-
return_value at Node 5	-	-	-	5	-	-	-
return_value at Node 3	-	-	-	-	8	-	-
return_value at Node 1	-	-	-	-	-	9	-

Key Moments - 3 Insights

Why do we use max(dfs(child), 0) instead of just dfs(child)?

Because negative path sums reduce the total, we ignore them by taking max with 0. See steps 3, 4, 9, 10, 14, 15 where None returns 0 and negative values are avoided.

Why do we update global max with node.val + left + right but return node.val + max(left, right)?

Global max considers paths passing through the node including both children (step 18). Return value is for parent path and can only include one child to keep path valid (step 20).

What happens if the tree has only one node?

The max path sum is the node's value itself. The recursion returns that value and updates global max accordingly (similar to step 5).

Visual Quiz - 3 Questions

Look at the execution table at step 18. What is the global max after visiting node 3?

A 8

B 5

C 12

D 11

💡 Hint

Check the 'Global Max' column at step 18 in the execution_table.

At which step does the DFS return the value 9 to the root node?

A Step 19

B Step 20

C Step 21

D Step 18

💡 Hint

Look at the 'Return Value' column and find when node 1 returns 9.

If we remove max(..., 0) in left and right calculations, what would happen to the global max?

A It could decrease due to negative paths

B It would stay the same

C It would always increase

D It would cause an error

💡 Hint

Refer to key_moments about ignoring negative path sums.

Concept Snapshot

DP on Trees Maximum Path Sum:
- Use DFS to explore all nodes
- At each node, get 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 answer is global max after full traversal

Full Transcript

This visualization shows how to find the maximum path sum in a binary tree using dynamic programming. We start at the root and recursively compute the maximum path sums from left and right children. Negative sums are ignored by taking max with zero. At each node, we calculate the maximum path sum passing through it by adding its value and the best sums from both children. We update a global maximum if this path is better. For returning to the parent, we only include the node's value plus the larger of the two child sums to keep the path valid. The process continues until all nodes are visited, and the global maximum holds the highest path sum found. Key points include ignoring negative paths, difference between updating global max and return value, and handling single-node trees.

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 between two nodes

B. The sum of all node values 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 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 sum of node values along any such path, which can start and end anywhere.

3. Final Answer:

   The largest sum of node values along any path between two nodes -> Option A

4. Quick Check:

   Maximum path sum = largest node value sum [OK]

Hint: Maximum path sum is about sums, not counts or single nodes [OK]

Common Mistakes:

• Confusing path sum with total tree sum
• Thinking path must start at root
• Considering only single nodes

2. Which of the following Python function signatures is correct for a recursive helper to find maximum path sum in a binary tree node?

def max_path_sum_helper(node: Optional[TreeNode]) -> int:

easy

A. def max_path_sum_helper(node: TreeNode) -> int:

B. def max_path_sum_helper(node: int) -> TreeNode:

C. def max_path_sum_helper(node: Optional[TreeNode]) -> int:

D. def max_path_sum_helper(node: TreeNode) -> None:

Solution

1. Step 1: Understand parameter type

   The node can be None (empty), so Optional[TreeNode] is correct to allow None.

2. Step 2: Understand return type

   The helper returns an integer representing max path sum from that node, so return type is int.

3. Final Answer:

   def max_path_sum_helper(node: Optional[TreeNode]) -> int: -> Option C

4. Quick Check:

   Optional node input and int output [OK]

Hint: Use Optional for nullable nodes and int return for sums [OK]

Common Mistakes:

• Not allowing None as input node
• Returning wrong type like None or TreeNode
• Using wrong parameter types

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

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_path_sum(root):
    max_sum = float('-inf')
    def helper(node):
        nonlocal max_sum
        if not node:
            return 0
        left = max(helper(node.left), 0)
        right = max(helper(node.right), 0)
        max_sum = max(max_sum, node.val + left + right)
        return node.val + max(left, right)
    helper(root)
    return max_sum

root = TreeNode(-10, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(max_path_sum(root))

medium

A. 35

B. 42

C. 27

D. 20

Solution

1. Step 1: Calculate max path sums for subtrees

   Left subtree max path sum is 9. Right subtree max path sum includes 20 + 15 + 7 = 42.

2. Step 2: Calculate max path sum including root

   Root value is -10, so max path sum including root is max(9, 0) + -10 + max(35, 0) = 34, but max_sum is updated to 42 from right subtree.

3. Final Answer:

   42 -> Option B

4. Quick Check:

   Max path sum = 15+20+7 = 42 [OK]

Hint: Ignore negative sums by max with 0 to maximize path [OK]

Common Mistakes:

• Adding negative paths instead of ignoring
• Confusing return value with max_sum
• Missing nonlocal max_sum update

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

def max_path_sum(root):
    max_sum = float('-inf')
    def helper(node):
        if not node:
            return 0
        left = helper(node.left)
        right = helper(node.right)
        max_sum = max(max_sum, node.val + left + right)
        return node.val + max(left, right)
    helper(root)
    return max_sum

medium

A. max_sum is not declared as nonlocal inside helper

B. helper returns wrong value for leaf nodes

C. Should return max_sum inside helper function

D. Missing base case for empty tree

Solution

1. Step 1: Check variable scope of max_sum

   max_sum is assigned inside helper but declared outside, so it needs 'nonlocal' to modify outer variable.

2. Step 2: Understand effect of missing nonlocal

   Without 'nonlocal', max_sum inside helper is local, so outer max_sum never updates, causing wrong result.

3. Final Answer:

   max_sum is not declared as nonlocal inside helper -> Option A

4. Quick Check:

   Use nonlocal to update outer max_sum [OK]

Hint: Declare nonlocal for outer variables modified inside nested functions [OK]

Common Mistakes:

• Forgetting nonlocal keyword
• Returning max_sum inside helper incorrectly
• Ignoring base case for None nodes

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. Add absolute values of nodes to maximize sum

B. Ignore negative values and return 0 as max path sum

C. Only consider paths starting at the root

D. Return the maximum single node value if all sums are negative

Solution

1. Step 1: Understand negative values impact

   If all nodes are negative, the maximum path sum is the largest (least negative) single node value, since no path sums to 0 and longer paths sum to less.

2. Step 2: Modify algorithm to track max single node

   Keep track of the maximum node value separately and return it if all path sums are negative.

3. Final Answer:

   Return the maximum single node value if all sums are negative -> Option D

4. Quick Check:

   Handle all-negative by max single node value [OK]

Hint: Track max node value separately to handle all negatives [OK]

Common Mistakes:

• Returning 0 when all nodes are negative
• Adding absolute values incorrectly
• Restricting paths to root only