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

Concept Flow - Maximum Path Sum in Binary Tree

Start at root node

↓

Calculate max path sum from left child

↓

Calculate max path sum from right child

↓

Calculate max path including current node

↓

Update global max if current path sum is higher

↓

Return max path sum for one side + current node

↓

Repeat for all nodes recursively

↓

Final max path sum stored globally

Start from the root, recursively find max path sums from left and right children, update global max with paths crossing current node, and return max single-side path sum upwards.

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.

Execution Table

Step	Operation	Node Visited	Left Max	Right Max	Current Path Sum	Global Max	Return Value	Visual State
1	Visit node	1	-	-	-	-∞	-	Node1(1)
2	Visit node	2	-	-	-	-∞	-	Node2(2)
3	Visit node	4	-	-	-	-∞	-	Node4(4)
4	Leaf node, return max(0, val)	4	0	0	4	4	4	Node4(4)
5	Back to node 2, calculate left max	2	4	-	-	4	-	Node2(2) with left=4
6	Visit node	5	-	-	-	4	-	Node5(5)
7	Leaf node, return max(0, val)	5	0	0	5	5	5	Node5(5)
8	Back to node 2, calculate right max	2	4	5	11	11	-	Node2(2) with left=4, right=5
9	Update global max	2	4	5	11	11	-	Max updated to 11
10	Return to parent (node 1)	2	4	5	11	11	7	Return 2 + max(4,5) = 7
11	Visit node	3	-	-	-	11	-	Node3(3)
12	Visit node	6	-	-	-	11	-	Node6(6)
13	Leaf node, return max(0, val)	6	0	0	6	11	6	Node6(6)
14	Visit node	7	-	-	-	11	-	Node7(7)
15	Leaf node, return max(0, val)	7	0	0	7	11	7	Node7(7)
16	Back to node 3, calculate left and right max	3	6	7	16	16	-	Node3(3) with left=6, right=7
17	Update global max	3	6	7	16	16	-	Max updated to 16
18	Return to parent (node 1)	3	6	7	16	16	10	Return 3 + max(6,7) = 10
19	Back to root node 1, calculate left and right max	1	7	10	18	18	-	Node1(1) with left=7, right=10
20	Update global max	1	7	10	18	18	-	Max updated to 18
21	Return from root	1	7	10	18	18	18	Return 1 + max(7,10) = 11
22	End	-	-	-	-	18	-	Final max path sum = 18

💡 All nodes visited, recursion ends with global max path sum 18

Variable Tracker

Variable	Start	After Step 4	After Step 7	After Step 8	After Step 10	After Step 13	After Step 15	After Step 16	After Step 18	After Step 20	Final
max_sum	-∞	4	5	11	11	11	11	16	16	18	18
left	-	0	4	4	7	7	6	6	7	7	7
right	-	0	0	5	5	5	7	7	7	10	10
return_value	-	4	5	7	7	6	7	10	10	11	18

Key Moments - 3 Insights

Why do we use 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 steps 4 and 7 where leaf nodes return their values, but if negative, 0 would be chosen.

Why do we update the 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 children. This is shown in steps 8, 16, and 20 where global max updates consider both sides plus current node.

What does the return value represent at each step?

It represents the maximum path sum for one side plus the current node, to be used by the parent. This is why in steps 10, 18, and 21 we return node.val + max(left, right).

Visual Quiz - 3 Questions

Look at the execution table at step 8. What is the current path sum at node 2?

A 4

B 7

C 11

D 5

💡 Hint

Check the 'Current Path Sum' column at step 8 in the execution_table.

At which step does the global max first update to 16?

A Step 16

B Step 18

C Step 20

D Step 8

💡 Hint

Look at the 'Global Max' column and find when it changes to 16.

If node 5 had a negative value, how would the return value at step 10 change?

A It would remain 7

B It would be less than 7

C It would be greater than 7

D It would be 0

💡 Hint

Recall that negative values are replaced by 0 in left/right max, so a negative node 5 reduces the max path sum at node 2.

Concept Snapshot

Maximum Path Sum in Binary Tree:
- Use DFS to explore all nodes.
- At each node, compute max path sums 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 traces the maximum path sum in a binary tree. Starting at the root, the algorithm recursively visits each node, calculating the maximum path sums from left and right children. Negative sums are ignored by taking max with zero. At each node, the sum of the node's value plus left and right max sums is compared to a global maximum and updated if larger. The function returns the maximum sum of one side plus the node's value to its parent. The execution table shows each step with node visits, path sums, and updates to the global maximum. Key moments clarify why negative sums are ignored, why the global max includes both sides, and what the return value means. The quiz tests understanding of these steps. The final maximum path sum is 18 for the example tree.

Practice

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

easy

A. The sum of values from root to the deepest leaf

B. The largest sum of values along any path between two nodes

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

D. The sum of all node values in the tree

Solution

1. Step 1: Understand the path definition

   A path can start and end at any nodes, not necessarily root or leaf.

2. Step 2: Define maximum path sum

   It is the highest sum of node values along any such path in the tree.

3. Final Answer:

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

4. Quick Check:

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

Hint: Remember path can start/end anywhere, not just root or leaf [OK]

Common Mistakes:

• Thinking path must start at root
• Confusing max node value with max path sum
• Summing all nodes instead of a path

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

easy

A. def maxPathSum(root: TreeNode) -> int:

B. def maxPathSum(root: int) -> TreeNode:

C. def maxPathSum(root: TreeNode) -> TreeNode:

D. def maxPathSum(root: int) -> int:

Solution

1. Step 1: Identify input type

   The function takes a TreeNode object representing the root of the tree.

2. Step 2: Identify return type

   The function returns an integer representing the maximum path sum.

3. Final Answer:

   def maxPathSum(root: TreeNode) -> int: -> Option A

4. Quick Check:

   Input=TreeNode, Output=int [OK]

Hint: Input is tree node, output is integer sum [OK]

Common Mistakes:

• Using int as input instead of TreeNode
• Returning TreeNode instead of int
• Mixing input and output types

3. Given the following binary tree and code snippet, what is the output?

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

def maxPathSum(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(maxPathSum(root))

medium

A. 35

B. 27

C. 42

D. 20

Solution

1. Step 1: Trace left and right subtree sums

   Left subtree max path sum is 9, right subtree max path sum is 20 + 15 + 7 = 42.

2. Step 2: Calculate max path sum including root

   Root (-10) + left (9) + right (20 + 15 + 7) = -10 + 9 + 22 = 21, but max path sum is updated at right subtree as 42.

3. Step 3: Identify maximum path sum

   The maximum path sum is 42, but the path that includes root is less than 42.

4. Final Answer:

   42 -> Option C

5. Quick Check:

   Max path sum = 42 [OK]

Hint: Add max(0, left/right) to avoid negative sums [OK]

Common Mistakes:

• Including negative sums from subtrees
• Confusing return value with max_sum
• Not using nonlocal for max_sum

4. Find the error in the following code snippet for maximum path sum in a binary tree:

def maxPathSum(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 should be declared as nonlocal inside helper

B. Return statement should be outside helper function

C. Base case should return None instead of 0

D. max_sum should be initialized to 0 instead of -inf

Solution

1. Step 1: Identify variable scope issue

   max_sum is assigned inside helper but declared outside, so Python treats it as local inside helper.

2. Step 2: Fix scope with nonlocal keyword

   Adding 'nonlocal max_sum' inside helper allows updating the outer max_sum variable.

3. Final Answer:

   max_sum should be declared as nonlocal inside helper -> Option A

4. Quick Check:

   Use nonlocal to update outer variable [OK]

Hint: Use nonlocal to modify outer variables inside nested functions [OK]

Common Mistakes:

• Forgetting nonlocal causes UnboundLocalError
• Changing base case return value incorrectly
• Initializing max_sum to 0 misses negative sums

5. You want to find the maximum path sum in a binary tree where some nodes have negative values. Which approach correctly handles negative values to find the maximum path sum?

hard

A. Only consider paths starting at root to leaf

B. Add all child sums regardless of sign to current node value

C. Replace negative node values with zero before calculation

D. Ignore negative child sums by taking max(child_sum, 0) before adding to current node

Solution

1. Step 1: Understand impact of negative values

   Negative sums reduce total path sum, so ignoring them improves max sum.

2. Step 2: Use max(child_sum, 0) to ignore negatives

   This ensures only positive contributions add to current node's path sum.

3. Step 3: Avoid altering original node values

   Replacing negatives with zero changes tree data and is incorrect.

4. Final Answer:

   Ignore negative child sums by taking max(child_sum, 0) before adding to current node -> Option D

5. Quick Check:

   Ignore negatives with max(child_sum, 0) [OK]

Hint: Use max(child_sum, 0) to skip negative paths [OK]

Common Mistakes:

• Adding negative sums reduces max path sum
• Modifying node values instead of sums
• Restricting paths to root-leaf only