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

Concept Flow - Path Sum Root to Leaf in Binary Tree

Start at root node

↓

Check if node is None?

Yes→Return False

No↓

Check if leaf node?

Yes→Check if sum equals target

↓

Return True/False

↓

Recurse left with updated sum

↓

Recurse right with updated sum

↓

Return left_result OR right_result

↓

Done

Start from root, check if node is leaf and sum matches target, else recurse left and right with updated sum, return True if any path matches.

Execution Sample

DSA Python

def hasPathSum(node, target):
    if not node:
        return False
    if not node.left and not node.right:
        return target == node.val
    return hasPathSum(node.left, target - node.val) or hasPathSum(node.right, target - node.val)

Checks if any root-to-leaf path sums to target by recursively subtracting node values.

Execution Table

Step	Operation	Current Node	Target Sum	Action	Result	Visual State
1	Start at root	5	22	Check if node is None	No	5
2	Check leaf	5	22	Is leaf?	No	5
3	Recurse left	4	17	Call hasPathSum(4, 22-5=17)	Pending	5 -> 4
4	Check leaf	4	17	Is leaf?	No	5 -> 4
5	Recurse left	11	13	Call hasPathSum(11, 17-4=13)	Pending	5 -> 4 -> 11
6	Check leaf	11	13	Is leaf?	Yes	5 -> 4 -> 11
7	Check sum	11	13	13 == 11?	False	5 -> 4 -> 11
8	Recurse right	None	13	Call hasPathSum(None, 13)	False	5 -> 4 -> 11
9	Return	11	13	Left or Right result	False	5 -> 4 -> 11
10	Recurse right	8	17	Call hasPathSum(8, 17-4=13)	Pending	5 -> 4 -> 8
11	Check leaf	8	13	Is leaf?	No	5 -> 4 -> 8
12	Recurse left	13	5	Call hasPathSum(13, 13-8=5)	Pending	5 -> 4 -> 8 -> 13
13	Check leaf	13	5	Is leaf?	Yes	5 -> 4 -> 8 -> 13
14	Check sum	13	5	5 == 13?	False	5 -> 4 -> 8 -> 13
15	Recurse right	None	5	Call hasPathSum(None, 5)	False	5 -> 4 -> 8 -> 13
16	Return	13	5	Left or Right result	False	5 -> 4 -> 8 -> 13
17	Return	8	13	Left or Right result	False	5 -> 4 -> 8
18	Return	4	17	Left or Right result	False	5 -> 4
19	Recurse right	8	17	Call hasPathSum(8, 22-5=17)	Pending	5 -> 8
20	Check leaf	8	17	Is leaf?	No	5 -> 8
21	Recurse left	13	9	Call hasPathSum(13, 17-8=9)	Pending	5 -> 8 -> 13
22	Check leaf	13	9	Is leaf?	Yes	5 -> 8 -> 13
23	Check sum	13	9	9 == 13?	False	5 -> 8 -> 13
24	Recurse right	4	9	Call hasPathSum(4, 9)	Pending	5 -> 8 -> 4
25	Check leaf	4	9	Is leaf?	Yes	5 -> 8 -> 4
26	Check sum	4	9	9 == 4?	False	5 -> 8 -> 4
27	Return	4	9	Left or Right result	False	5 -> 8 -> 4
28	Return	8	17	Left or Right result	False	5 -> 8
29	Return	5	22	Left or Right result	False	5
30	Recurse right	8	17	Call hasPathSum(8, 22-5=17)	Pending	5 -> 8
31	Check leaf	8	17	Is leaf?	No	5 -> 8
32	Recurse left	13	9	Call hasPathSum(13, 17-8=9)	Pending	5 -> 8 -> 13
33	Check leaf	13	9	Is leaf?	Yes	5 -> 8 -> 13
34	Check sum	13	9	9 == 13?	False	5 -> 8 -> 13
35	Recurse right	4	9	Call hasPathSum(4, 9)	Pending	5 -> 8 -> 4
36	Check leaf	4	9	Is leaf?	Yes	5 -> 8 -> 4
37	Check sum	4	9	9 == 4?	False	5 -> 8 -> 4
38	Return	4	9	Left or Right result	False	5 -> 8 -> 4
39	Return	8	17	Left or Right result	False	5 -> 8
40	Return	5	22	Left or Right result	False	5
41	End	None	None	No more nodes	False	Tree traversal complete

💡 All root-to-leaf paths checked, none sum to target 22, return False

Variable Tracker

Variable	Start	After Step 3	After Step 10	After Step 19	Final
Current Node	5	4	8	8	None
Target Sum	22	17	13	17	N/A
Result	N/A	Pending	Pending	Pending	False
Visual State	5	5 -> 4	5 -> 4 -> 8	5 -> 8	Traversal complete

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 steps 6 and 13 ensures we only compare sums when at a leaf node.

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

At each step, we reduce the target by the current node's value to check if the remaining path sums to the reduced target, as seen in steps 3, 10, and 19.

What happens if the node is None?

We return False immediately (step 8), meaning no path exists down that branch.

Visual Quiz - 3 Questions

Look at the execution table at step 6. Is the node a leaf and what is the result of the sum check?

A Node is leaf but sum does not match target

B Node is not leaf

C Node is leaf and sum matches target

D Node is None

💡 Hint

Check 'Is leaf?' and 'Check sum' columns at step 6 in execution_table

At which step does the function first return False because the node is None?

A Step 16

B Step 8

C Step 26

D Step 41

💡 Hint

Look for 'Call hasPathSum(None, ...)' and result False in execution_table

If the target sum was 20 instead of 22, how would the result at step 7 change?

A It would be True because 20 == 13

B It would be True because 20 == 11

C It would be False because 20 != 11

D It would be False because node is not leaf

💡 Hint

Compare target sum and node value at step 7 in execution_table

Concept Snapshot

Path Sum Root to Leaf in Binary Tree:
- Start at root node
- If node is leaf, check if target sum equals node value
- Else recurse left and right with target - node.val
- Return True if any path matches sum
- Return False if no path matches or node is None

Full Transcript

This concept checks if there is a root-to-leaf path in a binary tree where the sum of node values equals a target sum. We start at the root and recursively check each node. If the node is None, we return False. If the node is a leaf, we check if the remaining target sum equals the node's value. If yes, return True. Otherwise, we recurse on left and right children with the target sum reduced by the current node's value. We return True if any recursive call returns True, else False. The execution table shows each step, node visited, target sum at that step, and the result of checks. The variable tracker shows how current node and target sum change during recursion. Key moments clarify why leaf checks and sum subtraction are important. The visual quiz tests understanding of leaf checks, None nodes, and sum comparisons. This method ensures we only consider complete root-to-leaf paths for the sum.

Practice

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

easy

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

B. The maximum depth of the binary tree

C. The total number of leaf nodes in the tree

D. The sum of all node values in the 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: Identify what is being checked

   We check paths that start at the root and end at leaves, summing node values along the way, to see if any path matches the target sum.

3. Final Answer:

   If such a path exists, return true; otherwise, false -> Option A

4. Quick Check:

   Path sum check = existence of root-to-leaf path with target sum [OK]

Hint: Look for root-to-leaf paths matching target sum [OK]

Common Mistakes:

• Checking sum for any path, not just root-to-leaf
• Confusing leaf nodes with internal nodes
• Summing all nodes instead of a single path

2. Which of the following is the correct Python function signature to solve the Path Sum Root to Leaf problem using recursion?

easy

A. def has_path_sum(root: TreeNode, target_sum: int): return str

B. def has_path_sum(root, target_sum): return int

C. def has_path_sum(target_sum: int, root: TreeNode) -> bool:

D. def has_path_sum(root: TreeNode, target_sum: int) -> bool:

Solution

1. Step 1: Identify correct parameter order and types

   The function should take the root node first, then the target sum, matching the problem context.

2. Step 2: Confirm return type is boolean

   The function returns True or False depending on whether the path exists, so return type is bool.

3. Final Answer:

   def has_path_sum(root: TreeNode, target_sum: int) -> bool: -> Option D

4. Quick Check:

   Correct signature = root, target_sum, returns bool [OK]

Hint: Function takes root first, returns bool [OK]

Common Mistakes:

• Swapping parameter order
• Wrong return type annotation
• Missing type hints or incorrect ones

3. What will be the output of the following code snippet?

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def has_path_sum(root, target_sum):
    if not root:
        return False
    if not root.left and not root.right:
        return root.val == target_sum
    return has_path_sum(root.left, target_sum - root.val) or has_path_sum(root.right, target_sum - root.val)

root = TreeNode(5, TreeNode(4, TreeNode(11, TreeNode(7), TreeNode(2))), TreeNode(8, TreeNode(13), TreeNode(4, None, TreeNode(1))))
print(has_path_sum(root, 22))

medium

A. True

B. False

C. None

D. Error

Solution

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

   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

   The path 5->4->11->2 sums to 22, so function returns True.

3. Final Answer:

   True -> Option A

4. Quick Check:

   Path sum 22 exists = True [OK]

Hint: Check all root-to-leaf sums for target quickly [OK]

Common Mistakes:

• Not subtracting node values from target_sum
• Ignoring leaf node condition
• Returning None instead of boolean

4. Find the bug in this code snippet for checking path sum:

def has_path_sum(root, target_sum):
    if root is None:
        return False
    if root.left is None and root.right is None:
        return root.val == target_sum
    return has_path_sum(root.left, target_sum) or has_path_sum(root.right, target_sum)

medium

A. The base case should return True when root is None

B. The leaf node check is incorrect

C. The target_sum is not reduced by root.val in recursive calls

D. The function should return an integer sum

Solution

1. Step 1: Analyze recursive calls and target_sum usage

   The function calls itself with the same target_sum, not subtracting root.val, so sums are not updated correctly.

2. Step 2: Identify correct recursive call adjustment

   Each recursive call should reduce target_sum by root.val to track remaining sum needed.

3. Final Answer:

   target_sum not reduced by root.val in recursion -> Option C

4. Quick Check:

   Subtract node value from target_sum each step [OK]

Hint: Always subtract current node value from target_sum [OK]

Common Mistakes:

• Forgetting to update target_sum in recursion
• Returning wrong base case values
• Confusing leaf node condition

5. Given a binary tree where node values can be negative, zero, or positive, which modification is necessary to correctly solve the Path Sum Root to Leaf problem?

hard

A. Track the current path sum explicitly instead of subtracting from target

B. No modification needed; the standard approach works for all values

C. Use a breadth-first search instead of recursion

D. Ignore paths with negative sums

Solution

1. Step 1: Evaluate the standard subtraction approach with negatives

   The standard recursive method subtracts root.val from target_sum in recursive calls. This works correctly even with negative values because target_sum - root.val adjusts the remaining sum appropriately regardless of the sign.

2. Step 2: Confirm no changes needed

   No modification is necessary; the algorithm handles negative, zero, and positive values correctly without issues.

3. Final Answer:

   No modification needed; the standard approach works for all values -> Option B

4. Quick Check:

   Standard subtraction handles negatives [OK]

Hint: Standard recursion works with negative node values [OK]

Common Mistakes:

• Believing subtraction fails with negatives
• Using BFS unnecessarily for path sum
• Incorrectly pruning paths based on signs