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

Concept Flow - DP on Trees Maximum Path Sum

Start at root node

↓

Recursively compute max path sum from left child

↓

Recursively compute 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 to parent

↓

Repeat for all nodes

↓

Final global max is answer

We visit each node, compute max path sums from children, update global max path sum including current node, and return max path sum to parent.

Execution Sample

DSA Rust

fn max_path_sum(node: Option<&Box<TreeNode>>, max_sum: &mut i32) -> i32 {
    if node.is_none() { return 0; }
    let n = node.unwrap();
    let left = max_path_sum(n.left.as_ref(), max_sum).max(0);
    let right = max_path_sum(n.right.as_ref(), max_sum).max(0);
    *max_sum = (*max_sum).max(n.val + left + right);
    n.val + left.max(right)
}

This function recursively computes max path sums from left and right children, updates global max, and returns max path sum including current node.

Execution Table

Step	Operation	Node Visited	Left Max Path	Right Max Path	Current Max Path	Global Max Updated	Return Value	Visual State
1	Visit node 1	1	0	0	1	1	1	1
2	Visit node 2	2	0	0	2	2	2	1 -> 2
3	Visit node 4	4	0	0	4	4	4	1 -> 2 -> 4
4	Return to node 2	2	4	0	6	6	6	1 -> 2 -> 4
5	Visit node 3	3	0	0	3	6	3	1 -> 2 -> 4, 3
6	Visit node 5	5	0	0	5	6	5	1 -> 2 -> 4, 3 -> 5
7	Return to node 3	3	0	5	8	8	8	1 -> 2 -> 4, 3 -> 5
8	Return to node 1	1	6	8	15	15	9	Full tree: 1 -> 2 -> 4 and 1 -> 3 -> 5
9	End	None	-	-	-	15	-	Final max path sum is 15

💡 All nodes visited, recursion unwound, global max path sum is final answer.

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 7	After Step 8	Final
max_sum	-inf	1	6	8	15	15
Return value at node 4	-	4	4	4	4	4
Return value at node 2	-	-	6	6	6	6
Return value at node 5	-	-	-	5	5	5
Return value at node 3	-	-	-	8	8	8
Return value at node 1	-	-	-	-	9	9

Key Moments - 3 Insights

Why do we take max with 0 for left and right child path sums?

Because negative path sums reduce the total, we ignore them by taking max with 0. See rows 3 and 5 where left or right max path is 0 if negative or none.

Why do we update global max with n.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 rows 4, 7, and 8 where global max updates consider both sides.

What does the return value represent at each node?

It represents the max path sum including the current node and one of its subtrees to connect upwards. This is why we return n.val + max(left, right) as in rows 4, 7, and 8.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the return value from node 2?

A 2

B 4

C 6

D 1

💡 Hint

Check the 'Return Value' column at step 4 in execution_table.

At which step does the global max path sum first become 8?

A Step 5

B Step 7

C Step 6

D Step 8

💡 Hint

Look at the 'Global Max Updated' column in execution_table rows 5 to 8.

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

A It would be less than 8

B It would remain 8

C It would be more than 8

D It would be zero

💡 Hint

Recall that negative child paths are replaced by 0, so max path sum at node 3 depends on max of left and right child.

Concept Snapshot

DP on Trees Maximum Path Sum:
- Visit each node recursively
- Compute 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 max path sum in tree

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 the left and right children. Negative sums are ignored by taking the maximum with zero. At each node, we calculate the maximum path sum passing 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. The function returns the maximum path sum including the current node and one subtree to its parent. After visiting all nodes, the global maximum holds the maximum path sum in the tree.

Practice

1. What does the "maximum path sum" in a tree represent in the context of DP on Trees Maximum Path Sum?

easy

A. The largest sum of node values along any path between two nodes in the tree

B. The sum of all node values in the tree

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

D. The number of nodes in the longest path of the tree

Solution

1. Step 1: Understand the definition of path sum

   The path sum is the total of node values along a path connecting two nodes in the tree.

2. Step 2: Identify the maximum path sum meaning

   The maximum path sum is the largest such sum among all possible paths in the tree.

3. Final Answer:

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

4. Quick Check:

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

Hint: Maximum path sum is about sums on paths, not single nodes [OK]

Common Mistakes:

• Confusing maximum path sum with sum of all nodes
• Thinking it is just the max node value
• Counting number of nodes instead of sum

2. Which of the following Rust function signatures is correct for a recursive function that calculates the maximum path sum in a binary tree node defined as struct TreeNode { val: i32, left: Option, right: Option }?

easy

A. fn max_path_sum(node: Box<TreeNode>) -> Option<i32>

B. fn max_path_sum(node: TreeNode) -> i32

C. fn max_path_sum(node: &Option) -> i32

D. fn max_path_sum(node: &TreeNode) -> Option<i32>

Solution

1. Step 1: Understand ownership and borrowing in Rust

   Recursive tree functions usually borrow nodes to avoid ownership transfer and cloning.

2. Step 2: Match function signature to tree node type

   The tree node is wrapped in Option, so borrowing it as &Option is correct for recursion.

3. Final Answer:

   fn max_path_sum(node: &Option) -> i32 -> Option C

4. Quick Check:

   Borrow Option and return i32 [OK]

Hint: Use &Option to borrow nodes recursively [OK]

Common Mistakes:

• Taking ownership of node causing move errors
• Returning Option<i32> unnecessarily
• Using &TreeNode instead of &Option

3. Given the following Rust code snippet for maximum path sum in a binary tree, what is the output printed?

struct TreeNode {
    val: i32,
    left: Option,
    right: Option,
}

fn max_gain(node: &Option, max_sum: &mut i32) -> i32 {
    if let Some(n) = node {
        let left_gain = max_gain(&n.left, max_sum).max(0);
        let right_gain = max_gain(&n.right, max_sum).max(0);
        let price_newpath = n.val + left_gain + right_gain;
        *max_sum = (*max_sum).max(price_newpath);
        n.val + left_gain.max(right_gain)
    } else {
        0
    }
}

fn max_path_sum(root: &Option) -> i32 {
    let mut max_sum = i32::MIN;
    max_gain(root, &mut max_sum);
    max_sum
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: -10,
        left: Some(Box::new(TreeNode {
            val: 9,
            left: None,
            right: None,
        })),
        right: Some(Box::new(TreeNode {
            val: 20,
            left: Some(Box::new(TreeNode {
                val: 15,
                left: None,
                right: None,
            })),
            right: Some(Box::new(TreeNode {
                val: 7,
                left: None,
                right: None,
            })),
        })),
    }));
    println!("{}", max_path_sum(&root));
}

medium

A. 42

B. 35

C. 27

D. 20

Solution

1. Step 1: Calculate max path sums for each subtree

   Calculate max gains: - Left subtree (9): max gain = 9 - Right subtree: - Left child (15): max gain = 15 - Right child (7): max gain = 7 - Node 20: max gain = 20 + max(15,7) = 35 - Max path through 20: 20 + 15 + 7 = 42

2. Step 2: Calculate max path including root (-10)

   Root max gain = -10 + max(9, 35) = 25 Max path sum is max of: - Left subtree max: 9 - Right subtree max: 42 - Root path: 25 So max path sum = 42

3. Final Answer:

   42 -> Option A

4. Quick Check:

   Max path sum = 42 [OK]

Hint: Add node value plus max left/right gains, track max path [OK]

Common Mistakes:

• Ignoring negative values and not using max(0, gain)
• Adding gains incorrectly for path through root
• Confusing max gain with max path sum

4. The following Rust function attempts to compute the maximum path sum in a binary tree but contains a bug. What is the bug?

fn max_gain(node: &Option, max_sum: &mut i32) -> i32 {
    if let Some(n) = node {
        let left_gain = max_gain(&n.left, max_sum);
        let right_gain = max_gain(&n.right, max_sum);
        let price_newpath = n.val + left_gain + right_gain;
        *max_sum = (*max_sum).max(price_newpath);
        n.val + left_gain.max(right_gain)
    } else {
        0
    }
}

medium

A. It incorrectly updates max_sum inside recursion

B. It does not handle empty tree nodes

C. It returns the sum of left and right gains instead of max

D. It does not ignore negative gains by using max(0, gain)

Solution

1. Step 1: Analyze gain calculation for left and right subtrees

   The function uses left_gain and right_gain directly without ignoring negative values, which can reduce the path sum.

2. Step 2: Identify the fix for negative gains

   Correct approach is to use max_gain = max(0, recursive_gain) to ignore negative paths that reduce sum.

3. Final Answer:

   It does not ignore negative gains by using max(0, gain) -> Option D

4. Quick Check:

   Use max(0, gain) to avoid negative path sums [OK]

Hint: Always ignore negative gains with max(0, gain) [OK]

Common Mistakes:

• Forgetting to ignore negative subtree sums
• Updating max_sum incorrectly
• Returning wrong values from recursion

5. You want to modify the maximum path sum algorithm to find the maximum path sum that must include the root node in a binary tree. Which change should you make to the existing DP on Trees Maximum Path Sum approach?

hard

A. Use a global variable to store max sum and update it only when the path includes root and both children

B. Return the sum of the root value plus the maximum gain from either left or right subtree only, and track max sum accordingly

C. Calculate max path sum as usual but ignore paths that do not include the root node

D. Traverse the tree twice: once for max path sum and once for root-included path sum, then compare

Solution

1. Step 1: Understand the root-included path sum requirement

   The path must include the root node, so the path is root plus one subtree path (left or right), not both sides.

2. Step 2: Modify the gain calculation accordingly

   Return root.val + max(left_gain, right_gain) ignoring negative gains, and track max sum as this value.

3. Final Answer:

   Return the sum of the root value plus the maximum gain from either left or right subtree only, and track max sum accordingly -> Option B

4. Quick Check:

   Root-included max path = root + max(left, right) [OK]

Hint: Include root plus max one subtree gain only [OK]

Common Mistakes:

• Adding both left and right gains when root must be included
• Ignoring negative gains
• Trying to filter paths after calculation