Path Sum Root to Leaf in Binary Tree in DSA Python

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 you step on, and seeing if the total matches a treasure number at the end.

      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, subtract 5 from target sum 22

current node=5, remaining sum=17

Why: We reduce the target by the current node's value to check the rest of the path

Step 2: move to left child 4, subtract 4 from remaining sum 17

current node=4, remaining sum=13

Why: Continue down left path, updating remaining sum

Step 3: move to left child 11, subtract 11 from remaining sum 13

current node=11, remaining sum=2

Why: Keep going down left path

Step 4: move to left child 7, subtract 7 from remaining sum 2

current node=7, remaining sum=-5

Why: Reached leaf but sum does not match, so this path fails

Step 5: backtrack to 11, move to right child 2, subtract 2 from remaining sum 2

current node=2, remaining sum=0

Why: Check other leaf on this path; remaining sum zero means path found

Result:

Path found: 5 -> 4 -> 11 -> 2 with sum 22

Annotated Code

DSA Python

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
    # subtract current node value from target
    target_sum -= root.val
    # if leaf node, check if remaining sum is zero
    if not root.left and not root.right:
        return target_sum == 0
    # recursively check left and right subtree
    return has_path_sum(root.left, target_sum) or has_path_sum(root.right, target_sum)

# build tree from dry_run example
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
root.right.left = TreeNode(13)
root.right.right = TreeNode(4)
root.right.right.right = TreeNode(1)

result = has_path_sum(root, 22)
print(result)

if not root:

handle empty node base case

target_sum -= root.val

reduce target sum by current node value

if not root.left and not root.right:

check if current node is leaf

return target_sum == 0

if leaf, check if remaining sum is zero

return has_path_sum(root.left, target_sum) or has_path_sum(root.right, target_sum)

recurse left and right subtree to find valid 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 which also takes O(n), recursion is simpler but uses call stack

Edge Cases

empty tree

returns False because no paths exist

DSA Python

if not root:

single node equals target sum

returns True if node value equals target

DSA Python

if not root.left and not root.right: return target_sum == 0

no path matches target sum

returns False after checking all paths

DSA Python

return has_path_sum(root.left, target_sum) or has_path_sum(root.right, target_sum)

When to Use This Pattern

When asked if a root-to-leaf path sums to a target, use a recursive depth-first search subtracting node values from the target.

Common Mistakes

Mistake: Checking sum only at nodes, not verifying leaf nodes specifically
Fix: Only return True if remaining sum is zero at a leaf node

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 number.

Use when you need to verify if a path with a specific sum exists in a binary tree.

The key is to subtract node values as you go down and check sum only at leaf nodes.

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