Path Sum Root to Leaf in Binary Tree in DSA Rust - Build from Scratch

Path Sum Root to Leaf in Binary Tree

📖 Scenario: Imagine you have a family tree where each person has a number representing their age. You want to find if there is a path from the oldest ancestor (root) down to a youngest family member (leaf) where the sum of all ages equals a specific number.

🎯 Goal: You will build a simple binary tree in Rust and write code to check if there is a root-to-leaf path whose node values add up to a given sum.

📋 What You'll Learn

Create a binary tree node struct with value and optional left and right children

Create a sample binary tree with exact node values

Create a target sum variable

Write a recursive function to check if any root-to-leaf path sums to the target

Print the result as true or false

💡 Why This Matters

🌍 Real World

Checking path sums in trees is useful in decision trees, network routing, and financial calculations where cumulative values along paths matter.

💼 Career

Understanding tree traversal and recursion is fundamental for software engineers working with hierarchical data, algorithms, and system design.

1

Create the Binary Tree Node and Sample Tree

Define a struct called TreeNode with a field val of type i32, and two optional boxed children called left and right. Then create a variable called root that builds this exact tree:

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

DSA Rust

// Define TreeNode struct and create the root variable with the exact tree
// Your code here

Hint

Use Option> for left and right children to allow empty branches. Build the tree from bottom up inside Some(Box::new(TreeNode { ... })).

2

Create the Target Sum Variable

Create a variable called target_sum of type i32 and set it to 22.

DSA Rust

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

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 5,
        left: Some(Box::new(TreeNode {
            val: 4,
            left: Some(Box::new(TreeNode {
                val: 11,
                left: Some(Box::new(TreeNode { val: 7, left: None, right: None })),
                right: Some(Box::new(TreeNode { val: 2, left: None, right: None })),
            })),
            right: None,
        })),
        right: Some(Box::new(TreeNode {
            val: 8,
            left: Some(Box::new(TreeNode { val: 13, left: None, right: None })),
            right: Some(Box::new(TreeNode {
                val: 4,
                left: None,
                right: Some(Box::new(TreeNode { val: 1, left: None, right: None })),
            })),
        })),
    }));
    // Create target_sum variable here
    // Your code here

Hint

Use let target_sum: i32 = 22; inside main.

3

Write the Recursive Function to Check Path Sum

Write a function called has_path_sum that takes two parameters: node of type &Option> and sum of type i32. It returns a bool. The function should return true if there is a root-to-leaf path in the tree starting at node where the sum of node values equals sum. Otherwise, return false. Use recursion and check if the current node is a leaf and if the remaining sum equals the node's value. Call this function inside main with &root and target_sum.

DSA Rust

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

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 5,
        left: Some(Box::new(TreeNode {
            val: 4,
            left: Some(Box::new(TreeNode {
                val: 11,
                left: Some(Box::new(TreeNode { val: 7, left: None, right: None })),
                right: Some(Box::new(TreeNode { val: 2, left: None, right: None })),
            })),
            right: None,
        })),
        right: Some(Box::new(TreeNode {
            val: 8,
            left: Some(Box::new(TreeNode { val: 13, left: None, right: None })),
            right: Some(Box::new(TreeNode {
                val: 4,
                left: None,
                right: Some(Box::new(TreeNode { val: 1, left: None, right: None })),
            })),
        })),
    }));
    let target_sum: i32 = 22;

    // Your code here
}

Hint

Use pattern matching on node. If None, return false. If leaf node, check if remaining sum is zero. Otherwise, recursively check left and right children with updated sum.

4

Print the Result

Print the value of the variable result using println! inside main.

DSA Rust

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

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

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 5,
        left: Some(Box::new(TreeNode {
            val: 4,
            left: Some(Box::new(TreeNode {
                val: 11,
                left: Some(Box::new(TreeNode { val: 7, left: None, right: None })),
                right: Some(Box::new(TreeNode { val: 2, left: None, right: None })),
            })),
            right: None,
        })),
        right: Some(Box::new(TreeNode {
            val: 8,
            left: Some(Box::new(TreeNode { val: 13, left: None, right: None })),
            right: Some(Box::new(TreeNode {
                val: 4,
                left: None,
                right: Some(Box::new(TreeNode { val: 1, left: None, right: None })),
            })),
        })),
    }));
    let target_sum: i32 = 22;

    let result = has_path_sum(&root, target_sum);
    // Your code here
}

Hint

Use println!("{}", result); to print the boolean result.

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