DP on Trees Maximum Path Sum in DSA Rust

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 branches. At each fork, you choose the best path up to maximize your total height gain.

      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, where path can start and end at any nodes.

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

4(20) ↑ max_path_through=20

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

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

5(1) ↑ max_path_through=1

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

Step 3: At node 2 with value 2, max path through is 2 + max(20,1) = 22; max path using both children is 20 + 2 + 1 = 23

2(2) -> children 4(20),5(1) max_path_through=22 max_path_any=23

Why: We consider max path through one child for upward path, and sum both children plus node for max path anywhere

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

7(3) ↑ max_path_through=3

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

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

8(4) ↑ max_path_through=4

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

Step 6: At node 6 with value -25, max path through is -25 + max(3,4,0) = -21; max path using both children is 3 + (-25) + 4 = -18

6(-25) -> children 7(3),8(4) max_path_through=-21 max_path_any=-18

Why: Negative node value reduces path sum, but children can add positive values

Step 7: At node 3 with value 10, max path through is 10 + max(-21,0) = 10; max path using child 6 is max(-18,10)

3(10) -> child 6(-25) max_path_through=10 max_path_any=10

Why: We ignore negative max path through child for upward path

Step 8: At root node 1 with value 10, max path through is 10 + max(22,10) = 32; max path using both children is 22 + 10 + 10 = 42

1(10) -> children 2(22),3(10) max_path_through=32 max_path_any=42

Why: Combining best paths from both children plus root gives max path anywhere

Result:

Max path sum anywhere in tree is 42

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    children: Vec<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(TreeNode { val, children: vec![] }))
    }
}

struct Solution {
    max_sum: i32,
}

impl Solution {
    fn max_path_sum(root: Rc<RefCell<TreeNode>>) -> i32 {
        let mut sol = Solution { max_sum: i32::MIN };
        sol.dfs(&root);
        sol.max_sum
    }

    fn dfs(&mut self, node: &Rc<RefCell<TreeNode>>) -> i32 {
        let node_ref = node.borrow();
        let mut top_two = vec![];

        for child in &node_ref.children {
            let child_path = self.dfs(child);
            if child_path > 0 {
                top_two.push(child_path);
            }
        }

        top_two.sort_unstable_by(|a, b| b.cmp(a));
        if top_two.len() > 2 {
            top_two.truncate(2);
        }

        let max_single = if top_two.is_empty() { 0 } else { top_two[0] };
        let current_max = node_ref.val + max_single;

        let max_top = match top_two.len() {
            0 => node_ref.val,
            1 => node_ref.val + top_two[0],
            2 => node_ref.val + top_two[0] + top_two[1],
            _ => node_ref.val,
        };

        if max_top > self.max_sum {
            self.max_sum = max_top;
        }

        current_max
    }
}

fn main() {
    // Build tree from dry run example
    let root = TreeNode::new(10);
    let node2 = TreeNode::new(2);
    let node3 = TreeNode::new(10);
    let node4 = TreeNode::new(20);
    let node5 = TreeNode::new(1);
    let node6 = TreeNode::new(-25);
    let node7 = TreeNode::new(3);
    let node8 = TreeNode::new(4);

    node2.borrow_mut().children.push(node4);
    node2.borrow_mut().children.push(node5);
    node6.borrow_mut().children.push(node7);
    node6.borrow_mut().children.push(node8);
    node3.borrow_mut().children.push(node6);
    root.borrow_mut().children.push(node2);
    root.borrow_mut().children.push(node3);

    let result = Solution::max_path_sum(root);
    println!("{}", result);
}

for child in &node_ref.children { let child_path = self.dfs(child); if child_path > 0 { top_two.push(child_path); } }

collect max positive path sums from children

top_two.sort_unstable_by(|a, b| b.cmp(a)); if top_two.len() > 2 { top_two.truncate(2); }

keep top two max child paths for combining

let max_single = if top_two.is_empty() { 0 } else { top_two[0] }; let current_max = node_ref.val + max_single;

max path through node to parent uses best single child path

let max_top = match top_two.len() { 0 => node_ref.val, 1 => node_ref.val + top_two[0], 2 => node_ref.val + top_two[0] + top_two[1], _ => node_ref.val, };

max path anywhere through node may use two children plus node

if max_top > self.max_sum { self.max_sum = max_top; }

update global max path sum if current is better

current_max

return max path sum through node 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 checking all paths is O(n^2) or worse; DP on trees reduces to linear time

Edge Cases

Tree with single node

Returns the node's value as max path sum

DSA Rust

if top_two.is_empty() { 0 } else { top_two[0] }

Tree with all negative values

Returns the maximum single node value as max path sum

DSA Rust

self.max_sum initialized to i32::MIN and updated with max_top

Tree with zero or positive values

Combines positive child paths to maximize sum

DSA Rust

if child_path > 0 { top_two.push(child_path); }

When to Use This Pattern

When asked for maximum sum path in a tree that can start and end anywhere, use DP on trees by combining best child paths at each node.

Common Mistakes

Mistake: Including negative child paths in upward path sum causing lower totals
Fix: Ignore negative child paths by only adding positive child path sums

Mistake: Not considering paths that pass through the node combining two children
Fix: Track top two child paths and consider sum of both plus node value for max path anywhere

Summary

Finds the maximum sum of values along any path in a tree using dynamic programming.

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

The key insight is to combine the best one or two child paths at each node to find the global maximum.

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