Maximum Path Sum in Binary Tree in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Path Sum Calculation

What is the output of the following Rust code that calculates the maximum path sum in a binary tree?

DSA Rust

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

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

fn max_path_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    fn helper(node: Option<Rc<RefCell<TreeNode>>>, max_sum: &mut i32) -> i32 {
        if let Some(n) = node {
            let left = helper(n.borrow().left.clone(), max_sum).max(0);
            let right = helper(n.borrow().right.clone(), max_sum).max(0);
            let current = n.borrow().val + left + right;
            *max_sum = (*max_sum).max(current);
            n.borrow().val + left.max(right)
        } else {
            0
        }
    }
    let mut max_sum = i32::MIN;
    helper(root, &mut max_sum);
    max_sum
}

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

A 35

B 42

C 27

D 20

💡 Hint

Consider the path that includes the root's right subtree and its children.

The maximum path sum is 42, coming from the path 15 -> 20 -> 7, plus the root's value -10 is not included in the max path because it reduces the sum. The path 15 + 20 + 7 = 42 is the highest sum.

🧠 Conceptual

intermediate

Understanding Path Sum Components

In the maximum path sum problem, why do we use max(0, left_gain) and max(0, right_gain) when calculating the path sums?

A To avoid counting the root node twice in the path

B To ensure the path always includes both left and right children

C To ignore negative path sums that would decrease the total sum

D To count only the nodes with positive values in the tree

💡 Hint

Think about what happens if a subtree has a negative sum.

We use max(0, left_gain) and max(0, right_gain) to ignore any negative sums from subtrees because including a negative sum would reduce the overall path sum. This way, we only add positive contributions to the path.

🔧 Debug

advanced

Identify the Bug in Maximum Path Sum Implementation

What error will the following Rust code produce when calculating the maximum path sum, and why?

DSA Rust

fn max_path_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    fn helper(node: Option<Rc<RefCell<TreeNode>>>, max_sum: &mut i32) -> i32 {
        if let Some(n) = node {
            let left = helper(n.borrow().left.clone(), max_sum);
            let right = helper(n.borrow().right.clone(), max_sum);
            let current = n.borrow().val + left + right;
            *max_sum = (*max_sum).max(current);
            n.borrow().val + left.max(right)
        } else {
            0
        }
    }
    let mut max_sum = i32::MIN;
    helper(root, &mut max_sum);
    max_sum
}

A Incorrect maximum path sum because negative gains are not ignored

B Compilation error due to missing trait imports

C Stack overflow due to infinite recursion

D Runtime panic due to borrowing rules violation

💡 Hint

Check how negative values from subtrees are handled.

The code does not ignore negative gains from left or right subtrees, so it may include negative sums that reduce the maximum path sum, leading to incorrect results.

📝 Syntax

advanced

Syntax Error in Recursive Maximum Path Sum Function

Which option contains a syntax error in the Rust code for the maximum path sum helper function?

DSA Rust

fn helper(node: Option<Rc<RefCell<TreeNode>>>, max_sum: &mut i32) -> i32 {
    if let Some(n) = node {
        let left = helper(n.borrow().left.clone(), max_sum).max(0);
        let right = helper(n.borrow().right.clone(), max_sum).max(0);
        let current = n.borrow().val + left + right;
        *max_sum = (*max_sum).max(current);
        n.borrow().val + left.max(right)
    } else {
        0
    }
}

A if let Some(n) = node { ... } else { 0 }

B let right = helper(n.borrow().right.clone(), max_sum).max(0);

C n.borrow().val + left.max(right)

D let left = helper(n.borrow().left.clone(), max_sum.max(0));

💡 Hint

Check method call order and parentheses.

The method call order is incorrect in option D. It attempts to call .max(0) on max_sum (&mut i32), which does not have a max method. The max(0) should be applied to the result of helper.

🚀 Application

expert

Maximum Path Sum in a Complex Binary Tree

Given the following binary tree, what is the maximum path sum? Tree structure: 2 / \ -1 3 / \ 4 -5 / 1 Use the maximum path sum definition where the path can start and end at any node.

A 10

B 9

C 8

D 7

💡 Hint

Consider the path 1 -> 4 -> 3 -> 2.

The maximum path sum is 10, coming from the path 1 -> 4 -> 3 -> 2 (or 2 -> 3 -> 4 -> 1). The path sum is 1 + 4 + 3 + 2 = 10. Negative nodes like -1 and -5 are excluded.

Practice

1. What does the "Maximum Path Sum in Binary Tree" problem ask you to find?

easy

A. The longest path length in the binary tree

B. The number of leaf nodes in the binary tree

C. The highest sum of values along any path in the binary tree

D. The minimum value stored in the binary tree

Solution

1. Step 1: Understand the problem statement

   The problem asks for the maximum sum of node values along any path in the binary tree. A path can start and end at any node, but must be connected through parent-child links.

2. Step 2: Clarify what a path means

   A path can go downwards or upwards but cannot revisit nodes. The goal is to find the path with the largest sum of node values.

3. Final Answer:

   The highest sum of values along any path in the binary tree -> Option C

4. Quick Check:

   Maximum path sum means largest sum of connected nodes [OK]

Hint: Focus on sums of connected nodes, not just length [OK]

Common Mistakes:

• Confusing path length with path sum
• Thinking path must start at root
• Ignoring negative values in nodes

2. Which Rust function signature correctly represents a function to find 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(root: Option) -> i32

B. fn max_path_sum(root: TreeNode) -> Option<i32>

C. fn max_path_sum(root: &TreeNode) -> i32

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

Solution

1. Step 1: Understand Rust ownership and option types

   The tree root is usually wrapped in Option to allow for empty nodes and heap allocation.

2. Step 2: Choose correct function signature

   The function should accept Option and return i32 for the maximum path sum. Passing by value is common for ownership transfer.

3. Final Answer:

   fn max_path_sum(root: Option) -> i32 -> Option A

4. Quick Check:

   Option input and i32 output [OK]

Hint: Use Option for nullable tree nodes [OK]

Common Mistakes:

• Using TreeNode without Box causes size errors
• Returning Option<i32> unnecessarily
• Passing root by reference when ownership is needed

3. Given the following Rust code snippet for maximum path sum, what will be the output?

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

fn max_path_sum(root: Option) -> i32 {
    fn helper(node: &Option, max_sum: &mut i32) -> i32 {
        if let Some(n) = node {
            let left = helper(&n.left, max_sum).max(0);
            let right = helper(&n.right, max_sum).max(0);
            *max_sum = (*max_sum).max(n.val + left + right);
            n.val + left.max(right)
        } else {
            0
        }
    }
    let mut max_sum = i32::MIN;
    helper(&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. 20

B. 35

C. 27

D. 42

Solution

1. Step 1: Trace recursive helper calls and calculate sums

   Calculate max path sums for left and right subtrees, ignoring negative sums by max(0). For node 20, left=15, right=7, sum=20+15+7=42. For root -10, left max=9, right max=42, total= -10+9+42=41 but max_sum is 42 from node 20 subtree.

2. Step 2: Determine maximum path sum found

   The maximum path sum is 42 from path 15 -> 20 -> 7.

3. Final Answer:

   42 -> Option D

4. Quick Check:

   Max path sum = 42 [OK]

Hint: Ignore negative sums by max(0) to maximize path sum [OK]

Common Mistakes:

• Including negative sums in path
• Confusing max path sum with max root-to-leaf sum
• Miscomputing sums for left and right subtrees

4. Identify the bug in this Rust function snippet for maximum path sum and select the fix:

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

medium

A. Add .max(0) to left and right to ignore negative sums

B. Change return type to Option<i32>

C. Remove max_sum parameter and return max sum directly

D. Replace n.val + left.max(right) with n.val + left + right

Solution

1. Step 1: Identify problem with negative sums

   Without .max(0), negative sums from left or right subtrees reduce the path sum, which is incorrect for maximum path sum calculation.

2. Step 2: Fix by ignoring negative sums

   Adding .max(0) to left and right ensures negative sums are treated as zero, improving the maximum path sum calculation.

3. Final Answer:

   Add .max(0) to left and right to ignore negative sums -> Option A

4. Quick Check:

   Ignore negative sums with max(0) [OK]

Hint: Always ignore negative subtree sums with max(0) [OK]

Common Mistakes:

• Not handling negative values correctly
• Changing return type unnecessarily
• Summing left and right twice

5. You want to modify the maximum path sum function to also return the path nodes (values) that produce the maximum sum. Which approach is best to implement this in Rust?

hard

A. Return only max_sum and reconstruct path by traversing tree again after computation

B. Use a helper function returning a tuple of (max_sum, path_vec) and update global max with path

C. Store paths in a global mutable vector and update it inside recursion without returning

D. Use a stack to store nodes during recursion and pop when max sum is found

Solution

1. Step 1: Understand need to track path along with sums

   To return the path nodes, the helper must return both the max sum and the path that produces it.

2. Step 2: Use tuple return and update global max with path

   Returning (max_sum, path_vec) allows updating the global max sum and storing the corresponding path during recursion.

3. Final Answer:

   Use a helper function returning a tuple of (max_sum, path_vec) and update global max with path -> Option B

4. Quick Check:

   Return sum and path together for tracking [OK]

Hint: Return both sum and path as tuple from recursion [OK]

Common Mistakes:

• Using global mutable state without return
• Recomputing path after sum calculation
• Using stack incorrectly for path tracking