DP on Trees Maximum Path Sum in DSA Python - Build from Scratch

DP on Trees Maximum Path Sum

📖 Scenario: Imagine you are working with a network of connected devices arranged like a tree. Each device has a value representing its performance score. You want to find the path through the network that gives the highest total performance score. This path can start and end at any device but must follow the connections without loops.

🎯 Goal: Build a program that finds the maximum path sum in a tree using dynamic programming. You will create the tree, set up helper variables, write the core logic to compute the maximum path sum, and finally print the result.

📋 What You'll Learn

Create a tree using a dictionary called tree where keys are node ids and values are lists of connected node ids.

Create a dictionary called values with node ids as keys and their integer values as values.

Use a helper dictionary called max_single_path to store the maximum path sum starting from each node going downwards.

Implement a recursive function called dfs that calculates the maximum path sums using dynamic programming.

Print the maximum path sum found in the tree.

💡 Why This Matters

🌍 Real World

Finding the maximum path sum in a tree is useful in network optimization, where you want to find the best route or connection path with the highest combined score.

💼 Career

This problem is common in technical interviews and helps demonstrate understanding of trees, recursion, and dynamic programming.

1

Create the tree and node values

Create a dictionary called tree with these exact connections: 1: [2, 3], 2: [1, 4, 5], 3: [1], 4: [2], 5: [2]. Also create a dictionary called values with these exact entries: 1: 10, 2: 2, 3: 10, 4: 20, 5: 1.

DSA Python

# Create the tree dictionary and values dictionary
# Your code here

Hint

Use dictionaries to represent the tree connections and node values exactly as given.

2

Set up helper dictionary and global max variable

Create a dictionary called max_single_path with all node ids as keys and initial value float('-inf'). Also create a variable called max_path_sum and set it to float('-inf').

DSA Python

tree = {1: [2, 3], 2: [1, 4, 5], 3: [1], 4: [2], 5: [2]}
values = {1: 10, 2: 2, 3: 10, 4: 20, 5: 1}
# Create max_single_path dictionary and max_path_sum variable
# Your code here

Hint

Initialize max_single_path for all nodes with negative infinity and max_path_sum as negative infinity.

3

Implement DFS function to compute maximum path sums

Define a recursive function called dfs that takes node and parent as parameters. Inside, compute the maximum single path sums for children, update max_single_path[node], and update the global max_path_sum variable with the maximum path sum passing through node. Use the variables exactly as named.

DSA Python

tree = {1: [2, 3], 2: [1, 4, 5], 3: [1], 4: [2], 5: [2]}
values = {1: 10, 2: 2, 3: 10, 4: 20, 5: 1}
max_single_path = {node: float('-inf') for node in tree}
max_path_sum = float('-inf')
# Define dfs function to compute max path sums
# Your code here

Hint

Use recursion to explore children, calculate max single paths, and update the global max path sum.

4

Run DFS and print the maximum path sum

Call the dfs function starting from node 1 with parent -1. Then print the variable max_path_sum.

DSA Python

tree = {1: [2, 3], 2: [1, 4, 5], 3: [1], 4: [2], 5: [2]}
values = {1: 10, 2: 2, 3: 10, 4: 20, 5: 1}
max_single_path = {node: float('-inf') for node in tree}
max_path_sum = float('-inf')

def dfs(node, parent):
    global max_path_sum
    max_child_paths = []
    for child in tree[node]:
        if child == parent:
            continue
        dfs(child, node)
        max_child_paths.append(max_single_path[child])
    max_child_paths = [x for x in max_child_paths if x > 0]
    max_child_paths.sort(reverse=True)
    max_single_path[node] = values[node] + (max_child_paths[0] if max_child_paths else 0)
    max_top = values[node]
    if len(max_child_paths) >= 2:
        max_top += max_child_paths[0] + max_child_paths[1]
    elif len(max_child_paths) == 1:
        max_top += max_child_paths[0]
    if max_top > max_path_sum:
        max_path_sum = max_top

# Call dfs and print max_path_sum
# Your code here

Hint

Start DFS from node 1 with parent -1 and print the global max_path_sum.

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