DP on Trees Maximum Path Sum in DSA Python

Mental Model

We find the biggest sum of values along any path in a tree by checking each node's best paths through its children.

Analogy: Imagine climbing a mountain with many paths. At each fork, you choose the best way up and keep track of the highest peak you can reach by combining paths.

      1
     / \
    2   3
   / \   \
  4   5   6

Dry Run Walkthrough

Input: Tree: 1(10) with children 2(2), 3(10); 2 has children 4(20), 5(1); 3 has child 6(-25) with children 7(3), 8(4)

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

Step 1: Start at leaf node 4 with value 20, max path through 4 is 20

4(20) ↑

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

Step 2: At node 5 with value 1, max path through 5 is 1

5(1) ↑

Why: Leaf node max path is its own value

Step 3: At node 2, calculate max path through left child 4 (20) and right child 5 (1), max single path is max(20,1)+2=22, max path including both children is 20+2+1=23

2(2) -> left=4(20), right=5(1) ↑

Why: We consider paths through one child or both children plus current node

Step 4: At leaf node 7 with value 3, max path through 7 is 3

7(3) ↑

Why: Leaf node max path is its own value

Step 5: At leaf node 8 with value 4, max path through 8 is 4

8(4) ↑

Why: Leaf node max path is its own value

Step 6: At node 6 with value -25, max single path is max(3,4)+(-25) = -21, max path including both children is 3 + (-25) + 4 = -18, max single path is max(-25, -21) = -21

6(-25) -> left=7(3), right=8(4) ↑

Why: Negative node value reduces path sums, choose max single path carefully

Step 7: At node 3 with value 10, max single path is max(-21,0)+10=10, max path including both children is 10 + max(0,-21) + 0 = 10

3(10) -> child=6(-25) ↑

Why: Ignore negative child path sums by using 0 if negative

Step 8: At root node 1 with value 10, max single path is max(22,10)+10=32, max path including both children is 22 + 10 + 10 = 42, update global max to 42

1(10) -> left=2(2), right=3(10) ↑

Why: Combine best paths from left and right children plus current node

Result:

Maximum path sum is 42

Annotated Code

DSA Python

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

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.max_sum = float('-inf')

        def dfs(node):
            if not node:
                return 0
            left = max(dfs(node.left), 0)  # ignore negative paths
            right = max(dfs(node.right), 0)
            current_path = node.val + left + right
            self.max_sum = max(self.max_sum, current_path)  # update global max
            return node.val + max(left, right)  # max path down one side

        dfs(root)
        return self.max_sum

# Build tree from dry_run input
# Nodes: 1(10), 2(2), 3(10), 4(20), 5(1), 6(-25), 7(3), 8(4)
node7 = TreeNode(3)
node8 = TreeNode(4)
node6 = TreeNode(-25, node7, node8)
node4 = TreeNode(20)
node5 = TreeNode(1)
node2 = TreeNode(2, node4, node5)
node3 = TreeNode(10, None, node6)
root = TreeNode(10, node2, node3)

sol = Solution()
print(sol.maxPathSum(root))

left = max(dfs(node.left), 0) # ignore negative paths

calculate max path sum from left child, ignore if negative

right = max(dfs(node.right), 0)

calculate max path sum from right child, ignore if negative

current_path = node.val + left + right

sum path through current node including both children

self.max_sum = max(self.max_sum, current_path) # update global max

update global max path sum if current path is better

return node.val + max(left, right) # max path down one side

return max path sum going down one child for parent's use

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 tries all paths explicitly, costing O(n^2) or more; DP on trees reduces to O(n)

Edge Cases

Tree with all negative values

Algorithm picks the least negative single node as max path

DSA Python

left = max(dfs(node.left), 0)  # ignore negative paths

Single node tree

Returns the value of the single node as max path sum

DSA Python

if not node:
    return 0

Tree with zero values

Zero values are included if they improve path sum, else ignored

DSA Python

left = max(dfs(node.left), 0)

When to Use This Pattern

When asked for the maximum sum path in a tree that can start and end anywhere, use DP on trees with recursion to track max sums including and passing through each node.

Common Mistakes

Mistake: Not ignoring negative child path sums, causing lower max sums
Fix: Use max(child_sum, 0) to ignore negative paths

Mistake: Returning sum of both children to parent, which breaks path definition
Fix: Return node.val + max(left, right) to parent to keep path linear

Summary

Finds the maximum sum of values along any path in a binary tree.

Use when you need the highest sum path that can start and end at any nodes in the tree.

The key is to track max sums from children ignoring negative paths and combine them at each node.

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