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

Concept Flow - Path Sum Root to Leaf in Binary Tree

Start at root node

↓

Check if node is null?

Yes→Return false

No↓

Check if leaf node?

Yes→Check if sum equals node value

↓

Return true/false

↓

Subtract node value from sum

↓

Recurse left child

↓

Recurse right child

↓

Return left or right recursion result

Start from root, check if current node is leaf and sum matches. Otherwise, subtract node value and recurse left and right. Return true if any path matches.

Execution Sample

DSA C#

bool HasPathSum(TreeNode node, int sum) {
  if (node == null) return false;
  if (node.left == null && node.right == null) return sum == node.val;
  return HasPathSum(node.left, sum - node.val) || HasPathSum(node.right, sum - node.val);
}

Checks if any root-to-leaf path sums to the target value.

Execution Table

Step	Operation	Current Node	Remaining Sum	Leaf Check	Return Value	Visual State
1	Start at root	5	22	No	N/A	5 / \ 4 8
2	Recurse left	4	17	No	N/A	5 / \ 4 8
3	Recurse left	13	13	Yes	True	5 / \ 4 8 / 13
4	Return true up	4	17	No	True	5 / \ 4 8 / 13
5	Return true up	5	22	No	True	5 / \ 4 8 / 13
6	End	N/A	N/A	N/A	True	Path found: 5->4->13 sums to 22

💡 Returned true when leaf node 13 matched remaining sum 13.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
Current Node	5	5	4	13	4	5
Remaining Sum	22	22	17	13	17	22
Return Value	N/A	N/A	N/A	True	True	True

Key Moments - 3 Insights

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

Because only root-to-leaf paths count. The check at Step 3 ensures we only compare sums when at a leaf node.

Why do we subtract the node's value from sum before recursion?

Subtracting node.val updates the remaining sum needed for the path. This is shown in Remaining Sum column in Steps 2 and 3.

What happens if a node is null?

The function returns false immediately (Step 1), meaning no path through that branch.

Visual Quiz - 3 Questions

Look at the execution table, what is the Remaining Sum when visiting node 13 at Step 3?

A 22

B 17

C 13

D 14

💡 Hint

Check the 'Remaining Sum' column at Step 3 in the execution_table.

At which step does the function return true for the first time?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Return Value' column in the execution_table to find when true first appears.

If the target sum was 26 instead of 22, what would happen at Step 3?

A Return false because remaining sum 17 != 13

B Return true because 26 - 5 - 4 - 13 = 4

C Return true because 13 equals 26

D Return false because node 13 is not a leaf

💡 Hint

Consider how remaining sum changes and leaf check at Step 3 in execution_table.

Concept Snapshot

Path Sum Root to Leaf in Binary Tree:
- Start at root node
- If node is leaf, check if sum equals node value
- Else subtract node value from sum
- Recurse left and right children
- Return true if any path matches sum
- Return false if no path found

Full Transcript

This concept checks if there is a path from the root of a binary tree to any leaf where the sum of node values equals a target sum. The function starts at the root, and if the node is null, it returns false. If the node is a leaf, it compares the remaining sum to the node's value. If they match, it returns true. Otherwise, it subtracts the node's value from the sum and recursively checks the left and right children. The function returns true if any path matches the sum, otherwise false. The execution table shows step-by-step how the function moves through nodes 5, 4, and 13, updating the remaining sum and returning true when the leaf node 13 matches the remaining sum 13. Key moments clarify why leaf checks happen before sum comparison, why subtraction occurs before recursion, and what happens with null nodes. The visual quiz tests understanding of remaining sums, return steps, and behavior with different sums.

Practice

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

easy

A. The total number of nodes in the binary tree

B. The maximum depth of the binary tree

C. If there exists a root-to-leaf path with a sum equal to a given target

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

Solution

1. Step 1: Understand the problem statement

   The problem asks to check if any path from the root node down to any leaf node sums up exactly to a given target value.

2. Step 2: Identify what is being checked

   We are not asked for maximum depth, total nodes, or sum of all nodes, but specifically for a path sum equal to the target.

3. Final Answer:

   If there exists a root-to-leaf path with a sum equal to a given target -> Option C

4. Quick Check:

   Path sum check = If there exists a root-to-leaf path with a sum equal to a given target [OK]

Hint: Look for a path from root to leaf matching target sum [OK]

Common Mistakes:

• Confusing path sum with total tree sum
• Checking any path, not just root-to-leaf
• Looking for maximum depth instead

2. Which of the following C# method signatures correctly represents a function to check path sum in a binary tree node class?

easy

A. public bool HasPathSum(TreeNode root, int targetSum)

B. public int HasPathSum(TreeNode root, int targetSum)

C. public void HasPathSum(TreeNode root, int targetSum)

D. public string HasPathSum(TreeNode root, int targetSum)

Solution

1. Step 1: Determine the return type for path sum check

   The function should return true or false indicating if such a path exists, so return type must be bool.

2. Step 2: Check method signature correctness

   public bool HasPathSum(TreeNode root, int targetSum) returns bool and takes root node and target sum as parameters, matching the problem requirements.

3. Final Answer:

   public bool HasPathSum(TreeNode root, int targetSum) -> Option A

4. Quick Check:

   Return type bool for yes/no check = public bool HasPathSum(TreeNode root, int targetSum) [OK]

Hint: Return bool for yes/no path sum check [OK]

Common Mistakes:

• Using int or void return type instead of bool
• Returning string instead of boolean
• Incorrect parameter types or order

3. Given the following binary tree and targetSum = 22, what will the method HasPathSum(root, 22) return?

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

medium

A. Runtime error

B. true

C. null

D. false

Solution

1. Step 1: Identify root-to-leaf paths and their sums

   Check paths: 5->4->11->7 = 27, 5->4->11->2 = 22, 5->8->13 = 26, 5->8->4->1 = 18.

2. Step 2: Check if any path sum equals 22

   Path 5->4->11->2 sums to 22, so the method returns true.

3. Final Answer:

   true -> Option B

4. Quick Check:

   Path sum 22 exists = true [OK]

Hint: Sum each root-to-leaf path to find target [OK]

Common Mistakes:

• Ignoring leaf node condition
• Summing partial paths not ending at leaf
• Miscomputing sums of nodes

4. The following C# code attempts to check path sum but has a bug. What is the error?

public bool HasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    if (root.left == null && root.right == null) return root.val == targetSum;
    return HasPathSum(root.left, targetSum - root.val) || HasPathSum(root.right, targetSum - root.val);
}

medium

A. No bug; code works correctly

B. Should check for null root after subtracting value

C. Incorrect base case for leaf node check

D. Missing return statement in recursive calls

Solution

1. Step 1: Analyze base cases and recursion

   Code returns false if root is null, correctly handles leaf node by comparing value to targetSum, and recursively checks left and right subtrees with updated targetSum.

2. Step 2: Confirm correctness of logic

   All conditions and recursive calls are correct and return statements are present.

3. Final Answer:

   No bug; code works correctly -> Option A

4. Quick Check:

   Code logic matches problem requirements = No bug; code works correctly [OK]

Hint: Check base cases and recursive returns carefully [OK]

Common Mistakes:

• Forgetting to subtract node value from targetSum
• Missing return keyword in recursion
• Incorrect leaf node condition

5. You want to find all root-to-leaf paths in a binary tree where the sum of node values equals a target sum. Which approach best extends the path sum check to collect all such paths?

hard

A. Sum all nodes and compare to target sum once traversal ends

B. Use BFS and stop at first path matching the sum

C. Use recursion without tracking path, just return true/false

D. Use DFS with a list to track current path and add to result when sum matches at leaf

Solution

1. Step 1: Understand the requirement to collect all paths

   We need to find all root-to-leaf paths with sum equal to target, so we must track the current path during traversal.

2. Step 2: Choose the correct traversal and tracking method

   DFS with a list to store nodes along the current path allows backtracking and collecting all valid paths when leaf and sum conditions are met.

3. Final Answer:

   Use DFS with a list to track current path and add to result when sum matches at leaf -> Option D

4. Quick Check:

   Track paths with DFS and list = Use DFS with a list to track current path and add to result when sum matches at leaf [OK]

Hint: Track path nodes during DFS to collect all valid paths [OK]

Common Mistakes:

• Using BFS which is less natural for path tracking
• Not tracking path nodes, only sums
• Stopping at first found path instead of all