Path Sum Root to Leaf in Binary Tree in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of path sum check for a simple tree

What is the output of the following code that checks if there is a root-to-leaf path with the given sum?

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
    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)

# Tree:
#     5
#    / \
#   4   8
#  /   / \
# 11  13  4
# Target sum = 22
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.right.left = TreeNode(13)
root.right.right = TreeNode(4)

print(has_path_sum(root, 22))

A True

B Error

C None

D False

💡 Hint

Check if any root-to-leaf path sums exactly to 22.

The root-to-leaf paths sum to 20 (5-4-11), 26 (5-8-13), and 17 (5-8-4). None equal 22, so output is False (option D).

❓ Predict Output

intermediate

Output of path sum check with negative values

What is the output of this code that checks for a path sum including negative values?

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
    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)

# Tree:
#     1
#    / \
#  -2   -3
#  / \    \
# 1   3   -2
# Target sum = -1
root = TreeNode(1)
root.left = TreeNode(-2)
root.right = TreeNode(-3)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.right = TreeNode(-2)

print(has_path_sum(root, -1))

A False

B True

C None

D Error

💡 Hint

Consider all root-to-leaf paths and their sums.

The root-to-leaf paths sum to 0 (1--2-1), 2 (1--2-3), and -4 (1--3--2). None equal -1, so output is False (option A).

🔧 Debug

advanced

Identify the error in path sum function

What error does this code raise when checking for a path sum?

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 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 - root.val) and has_path_sum(root.right, target_sum - root.val)

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(has_path_sum(root, 3))

A Logical error: incorrect use of 'and' instead of 'or'

B Returns True

C RecursionError (maximum recursion depth exceeded)

D Returns False

💡 Hint

Check the logical operator used to combine recursive calls.

The function uses 'and' to combine left and right subtree results, but it should use 'or' because a path sum can be found in either subtree. Using 'and' means both subtrees must have a path sum, which is logically incorrect.

🧠 Conceptual

advanced

Number of root-to-leaf paths with given sum

Given a binary tree, how would you find the number of root-to-leaf paths where the sum of node values equals a target sum?

A Use a stack to store sums but ignore leaf nodes

B Use recursion to explore all paths, increment count when a leaf node's path sum equals target

C Use recursion but only check left subtree for the sum

D Use breadth-first search and stop at first path matching target sum

💡 Hint

Think about exploring all paths and counting matches at leaves.

To count all root-to-leaf paths with a given sum, you must explore every path recursively and increment a counter when a leaf node's path sum matches the target. BFS stopping at first match or ignoring leaf nodes won't count all paths.

🚀 Application

expert

Find all root-to-leaf paths with given sum

Which code snippet correctly returns all root-to-leaf paths where the sum of node values equals the target sum?

DSA Python

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

# Choose the correct function implementation:

A

def path_sum(root, target_sum):
    if not root:
        return []
    if not root.left and not root.right and root.val == target_sum:
        return [[root.val]]
    left_paths = path_sum(root.left, target_sum - root.val)
    right_paths = path_sum(root.right, target_sum - root.val)
    return left_paths + right_paths

B

def path_sum(root, target_sum):
    paths = []
    stack = [(root, [root.val], root.val)]
    while stack:
        node, path, total = stack.pop()
        if not node.left and not node.right and total == target_sum:
            paths.append(path)
        if node.left:
            stack.append((node.left, path + [node.left.val], total + node.left.val))
        if node.right:
            stack.append((node.right, path + [node.right.val], total + node.right.val))
    return paths

C

def path_sum(root, target_sum):
    result = []
    def dfs(node, current_path, current_sum):
        if not node:
            return
        current_path.append(node.val)
        current_sum += node.val
        if not node.left and not node.right and current_sum == target_sum:
            result.append(list(current_path))
        else:
            dfs(node.left, current_path, current_sum)
            dfs(node.right, current_path, current_sum)
        current_path.pop()
    dfs(root, [], 0)
    return result

D

def path_sum(root, target_sum):
    result = []
    def dfs(node, current_path):
        if not node:
            return
        current_path.append(node.val)
        if not node.left and not node.right and sum(current_path) == target_sum:
            result.append(list(current_path))
        dfs(node.left, current_path)
        dfs(node.right, current_path)
        current_path.pop()
    dfs(root, [])
    return result

💡 Hint

Look for a solution that avoids recomputing sums repeatedly and backtracks properly.

Option C uses DFS with backtracking, accumulating sum as it goes, and appends a copy of the path when the sum matches at a leaf. Option C misses adding root.val to paths. Option C uses stack but misses initial root check if root is None. Option C recomputes sum(current_path) repeatedly, which is inefficient.

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