Path Sum Root to Leaf in Binary Tree in DSA Rust - Execution Trace

Concept Flow - Path Sum Root to Leaf in Binary Tree

Start at root node

↓

Check if node is leaf

↓

Check sum == target

↓

Go right child

↓

Return True/False

↓

Combine results

↓

Return final result

Start from the root, check if current node is a leaf and if the path sum equals target. If not leaf, recursively check left and right children, combining results to find if any path matches.

Execution Sample

DSA Rust

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

Checks if there is a root-to-leaf path in the binary tree where the sum of node values equals the target.

Execution Table

Step	Operation	Current Node	Target Sum	Action	Visual State
1	Start at root	5	22	Check if leaf	5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1
2	Not leaf	5	22	Go left child with target 17 (22-5)	Same tree, focus on node 4
3	At node 4	4	17	Not leaf, go left child with target 13 (17-4)	Focus on node 11
4	At node 11	11	13	Not leaf, go left child with target 2 (13-11)	Focus on node 7
5	At node 7	7	2	Leaf node, check if 7 == 2	Leaf node 7
6	Result	7	2	False, backtrack to node 11	Back to node 11
7	At node 11	11	13	Go right child with target 2 (13-11)	Focus on node 2
8	At node 2	2	2	Leaf node, check if 2 == 2	Leaf node 2
9	Result	2	2	True, path found: 5->4->11->2	Path highlighted
10	Combine results	11	13	Left false, right true => true	Return true up
11	Combine results	4	17	Left true => true	Return true up
12	Combine results	5	22	Left true => true	Final result true
13	End	N/A	N/A	Return true	Done

💡 Returned true when path sum 5->4->11->2 equals target 22 at leaf node 2

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 7	After Step 8	Final
Current Node	5	4	11	7	7	11	2	N/A
Target Sum	22	17	13	2	2	2	2	N/A
Result	N/A	N/A	N/A	N/A	False	N/A	True	True

Key Moments - 3 Insights

Why do we check if the node is a leaf before comparing the sum?

Because only root-to-leaf paths count. The check at step 5 and 8 ensures we only compare the sum when at a leaf node, as shown in execution_table rows 5 and 8.

Why do we subtract the current node's value from the target sum when going deeper?

Subtracting the node's value updates the remaining sum needed. This is shown in execution_table steps 2, 3, and 4 where target sum decreases as we go down the tree.

What happens if one child path returns true and the other false?

We use logical OR to combine results. If either left or right subtree returns true, the function returns true, as seen in steps 10 and 11.

Visual Quiz - 3 Questions

Look at the execution table, what is the target sum when the function checks node 11 for the first time?

A 17

B 13

C 22

D 2

💡 Hint

Check the 'Target Sum' column at step 3 in the execution_table.

At which step does the function find a leaf node where the path sum equals the target?

A Step 5

B Step 6

C Step 8

D Step 10

💡 Hint

Look for the step where 'Leaf node, check if value == target' is true in the execution_table.

If the left child of node 4 was None, how would the execution_table change at step 3?

A Step 3 would check right child of 4 instead

B Step 3 would return false immediately

C Step 3 would skip node 4 and go to node 8

D Step 3 would cause an error

💡 Hint

Recall that if left child is None, the function tries the right child as per the OR condition in the code.

Concept Snapshot

Path Sum Root to Leaf in Binary Tree:
- Start at root node
- At each node, subtract node value from target sum
- If leaf node, check if remaining sum equals node value
- Recursively check left and right children
- Return true if any path matches target sum
- Uses recursion and logical OR to combine results

Full Transcript

This concept checks if a binary tree has a root-to-leaf path where the sum of node values equals a target. Starting at the root, we check if the node is a leaf. If yes, we compare the node's value to the remaining target sum. If not, we subtract the node's value from the target and recursively check left and right children. The function returns true if any path matches the target sum. The execution table shows step-by-step traversal and sum updates, highlighting how the function backtracks and combines results. Key moments clarify why leaf checks and sum subtraction are essential. The visual quiz tests understanding of target sum updates, leaf checks, and behavior when children are missing.

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