Path Sum Root to Leaf in Binary Tree in DSA Rust

Mental Model

We want to check if there is a path from the top of the tree to any bottom leaf where the numbers add up to a target sum.

Analogy: Imagine walking down a tree from the top branch to the bottom leaves, adding numbers on each branch. We want to see if any path adds up exactly to a certain number.

    5
   / \
  4   8
 /   / \
11  13  4
/  \      \
7    2      1

Dry Run Walkthrough

Input: tree: 5->4->11->7 (left leaf), target sum = 22

Goal: Find if any root-to-leaf path sums to 22

Step 1: start at root node 5, current sum needed is 22

5 (need 22)

Why: We begin at the top and want to find a path summing to 22

Step 2: go left to node 4, subtract 5 from sum, now need 17

5 -> 4 (need 17)

Why: We move down left branch, updating remaining sum

Step 3: go left to node 11, subtract 4, now need 13

5 -> 4 -> 11 (need 13)

Why: Continue down left path, updating sum

Step 4: go left to node 7, subtract 11, now need 2

5 -> 4 -> 11 -> 7 (need 2)

Why: Reached leaf candidate, check if sum matches

Step 5: 7 is leaf but need 2, path sum not matched, backtrack

back to 11

Why: Leaf sum does not match target, try other paths

Step 6: go right to node 2 from 11, subtract 11, now need 2

5 -> 4 -> 11 -> 2 (need 2)

Why: Try other leaf on this branch

Step 7: 2 is leaf and need 2, path sum matched

5 -> 4 -> 11 -> 2 (need 2)

Why: Found a path where sum equals target

Result:

5 -> 4 -> 11 -> 2 -> null (path sum 22 found)

Annotated Code

DSA Rust

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

#[derive(Debug, Clone)]
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 has_path_sum(root: Option<Rc<RefCell<TreeNode>>>, target_sum: i32) -> bool {
    if root.is_none() {
        return false; // empty tree means no path
    }
    let node = root.unwrap();
    let node_ref = node.borrow();

    // Check if leaf node
    if node_ref.left.is_none() && node_ref.right.is_none() {
        return node_ref.val == target_sum; // leaf matches sum?
    }

    // Recursively check left and right subtrees with reduced sum
    let left_has = has_path_sum(node_ref.left.clone(), target_sum - node_ref.val);
    let right_has = has_path_sum(node_ref.right.clone(), target_sum - node_ref.val);

    left_has || right_has
}

fn main() {
    // Build tree:
    //      5
    //     / \
    //    4   8
    //   /   / \
    // 11  13  4
    // / \      \
    //7   2      1

    let root = TreeNode::new(5);
    let n4 = TreeNode::new(4);
    let n8 = TreeNode::new(8);
    let n11 = TreeNode::new(11);
    let n13 = TreeNode::new(13);
    let n4_2 = TreeNode::new(4);
    let n7 = TreeNode::new(7);
    let n2 = TreeNode::new(2);
    let n1 = TreeNode::new(1);

    root.borrow_mut().left = Some(n4.clone());
    root.borrow_mut().right = Some(n8.clone());
    n4.borrow_mut().left = Some(n11.clone());
    n8.borrow_mut().left = Some(n13.clone());
    n8.borrow_mut().right = Some(n4_2.clone());
    n11.borrow_mut().left = Some(n7.clone());
    n11.borrow_mut().right = Some(n2.clone());
    n4_2.borrow_mut().right = Some(n1.clone());

    let target_sum = 22;
    let result = has_path_sum(Some(root), target_sum);
    println!("{}", result);
}

if root.is_none() { return false; }

handle empty tree base case

if node_ref.left.is_none() && node_ref.right.is_none() { return node_ref.val == target_sum; }

check if current node is leaf and if its value matches remaining sum

let left_has = has_path_sum(node_ref.left.clone(), target_sum - node_ref.val);

recurse left subtree with reduced sum

let right_has = has_path_sum(node_ref.right.clone(), target_sum - node_ref.val);

recurse right subtree with reduced sum

left_has || right_has

return true if any subtree has matching path

Output

true

Complexity Analysis

Time: O(n) because we visit each node once to check paths

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to iterative BFS, recursion is simpler but uses call stack; BFS uses queue and may use more memory in wide trees

Edge Cases

empty tree

returns false because no paths exist

DSA Rust

if root.is_none() { return false; }

single node tree where node value equals target sum

returns true because root is leaf and matches sum

DSA Rust

if node_ref.left.is_none() && node_ref.right.is_none() { return node_ref.val == target_sum; }

single node tree where node value does not equal target sum

returns false because leaf value does not match sum

DSA Rust

if node_ref.left.is_none() && node_ref.right.is_none() { return node_ref.val == target_sum; }

When to Use This Pattern

When asked if a root-to-leaf path sums to a target, use a depth-first search that subtracts node values from the target as you go down.

Common Mistakes

Mistake: Checking sum only at root or non-leaf nodes
Fix: Only check if sum matches at leaf nodes to ensure full path

Mistake: Not subtracting current node value from target sum before recursion
Fix: Subtract current node's value from target sum before recursive calls

Summary

Checks if any root-to-leaf path sums to a given target in a binary tree.

Use when you need to verify if a path with a specific sum exists from top to bottom.

The key is to subtract node values from the target sum as you go down and check only at leaves.

Practice

1. What does the "Path Sum Root to Leaf" problem ask you to find in a binary tree?

easy

A. The maximum depth of the binary tree

B. If there exists a root-to-leaf path with a sum equal to a target value

C. The total number of nodes in the binary tree

D. The sum of all node values in the binary tree

Solution

1. Step 1: Understand the problem statement

   The problem asks if there is any path from the root node down to any leaf node where the sum of the node values equals a given target sum.

2. Step 2: Differentiate from other tree properties

   This is different from finding the maximum depth, counting nodes, or summing all nodes. It specifically checks for a path sum.

3. Final Answer:

   If there exists a root-to-leaf path with a sum equal to a target value -> Option B

4. Quick Check:

   Path sum means root-to-leaf sum check = A [OK]

Hint: Focus on root-to-leaf paths and their sums [OK]

Common Mistakes:

• Confusing path sum with total tree sum
• Checking any path, not just root-to-leaf
• Mixing depth or node count with sum

2. Which of the following Rust function signatures correctly represents a function to check path sum in a binary tree node defined as struct TreeNode { val: i32, left: Option, right: Option }?

easy

A. fn has_path_sum(root: Option<TreeNode>, sum: i32) -> bool

B. fn has_path_sum(root: TreeNode, sum: i32) -> i32

C. fn has_path_sum(root: Option, sum: i32) -> bool

D. fn has_path_sum(root: &TreeNode, sum: i32) -> Option<i32>

Solution

1. Step 1: Analyze the tree node ownership and option usage

   The tree nodes are wrapped in Option to allow for empty children and heap allocation. The function should accept Option to handle empty trees.

2. Step 2: Check return type and parameters

   The function returns a boolean indicating if a path sum exists. So the signature fn has_path_sum(root: Option, sum: i32) -> bool matches the problem.

3. Final Answer:

   fn has_path_sum(root: Option, sum: i32) -> bool -> Option C

4. Quick Check:

   Correct ownership and return type = D [OK]

Hint: Use Option for nullable tree nodes [OK]

Common Mistakes:

• Using TreeNode directly without Option or Box
• Wrong return type (not bool)
• Passing references incorrectly

3. Given the following Rust code, what is the output?

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

fn has_path_sum(root: Option, sum: i32) -> bool {
    match root {
        None => false,
        Some(node) => {
            if node.left.is_none() && node.right.is_none() {
                return node.val == sum;
            }
            has_path_sum(node.left, sum - node.val) || has_path_sum(node.right, sum - node.val)
        }
    }
}

fn main() {
    let leaf = TreeNode { val: 5, left: None, right: None };
    let root = TreeNode {
        val: 4,
        left: Some(Box::new(leaf)),
        right: None,
    };
    println!("{}", has_path_sum(Some(Box::new(root)), 9));
}

medium

A. Compilation error

B. false

C. Runtime panic

D. true

Solution

1. Step 1: Trace the path sum calculation

   The tree has root 4 with left child 5. The target sum is 9. The path 4 -> 5 sums to 9, so the function returns true.

2. Step 2: Confirm leaf node check and recursion

   At leaf node 5, it checks if 5 == 9 - 4 = 5, which is true, so returns true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   4 + 5 = 9 matches sum = true [OK]

Hint: Check leaf node sums carefully [OK]

Common Mistakes:

• Ignoring leaf node condition
• Subtracting sum incorrectly
• Confusing Option handling

4. The following Rust function is intended to check if a path sum exists but has a bug. What is the bug?

fn has_path_sum(root: Option, sum: i32) -> bool {
    if root.is_none() {
        return false;
    }
    let node = root.unwrap();
    if node.left.is_none() && node.right.is_none() {
        return node.val == sum;
    }
    has_path_sum(node.left, sum - node.val) && has_path_sum(node.right, sum - node.val)
}

medium

A. Using && instead of || for recursive calls

B. Unwrapping Option without checking None

C. Not handling empty tree case

D. Incorrect sum subtraction

Solution

1. Step 1: Analyze recursive call logic

   The function uses logical AND (&&) to combine left and right subtree results, but the problem requires checking if any path exists, so logical OR (||) is correct.

2. Step 2: Understand impact of && vs ||

   Using && means both left and right paths must have the sum, which is incorrect. Only one path needs to match.

3. Final Answer:

   Using && instead of || for recursive calls -> Option A

4. Quick Check:

   Path sum needs OR (||), not AND (&&) [OK]

Hint: Use || to check any path, not all paths [OK]

Common Mistakes:

• Using && instead of ||
• Unwrapping Option without safe check
• Ignoring leaf node condition

5. You want to modify the path sum function to return all root-to-leaf paths where the sum equals the target. Which approach is best to implement this in Rust?

hard

A. Use backtracking with a mutable vector to store current path and a vector of vectors for results

B. Use a global variable to store paths and update it in recursion

C. Return a boolean and print paths inside the function

D. Use iterative BFS traversal without recursion

Solution

1. Step 1: Understand the requirement for all paths

   To find all root-to-leaf paths with a given sum, we need to explore all paths and store those matching the sum.

2. Step 2: Choose backtracking with mutable vectors

   Backtracking allows building paths step-by-step, storing current path in a mutable vector, and adding copies to results when sum matches.

3. Final Answer:

   Use backtracking with a mutable vector to store current path and a vector of vectors for results -> Option A

4. Quick Check:

   Backtracking with path storage = B [OK]

Hint: Backtrack paths, store copies when sum matches [OK]

Common Mistakes:

• Using global variables (not idiomatic in Rust)
• Printing instead of returning paths
• Trying BFS which is complex for path tracking