Path Sum Root to Leaf in Binary Tree in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a 'root-to-leaf path' in a binary tree?

A root-to-leaf path is a sequence of nodes starting from the root node and ending at any leaf node, where a leaf node has no children.

beginner

What does the 'Path Sum Root to Leaf' problem ask you to find?

It asks whether there exists a root-to-leaf path in the binary tree such that the sum of the node values along the path equals a given target sum.

beginner

How do you check if a node is a leaf node in a binary tree?

A node is a leaf if it has no left child and no right child.

intermediate

Why do we subtract the node's value from the target sum when moving down the tree?

Subtracting the node's value updates the remaining sum needed to reach the target along the current path, helping to check if the path sum matches at the leaf.

intermediate

What is the base case for the recursive solution to the Path Sum problem?

The base case is when the current node is null (no node), which means no path, so return False. Another base case is when the node is a leaf and the remaining sum equals the node's value, then return True.

What should you return if you reach a null node in the Path Sum problem?

A True

B False

C The target sum

D The node's value

Reaching a null node means no path exists here, so return False.

When do you check if the path sum equals the target sum?

A At every node

B Only at the root

C Only at leaf nodes

D At every left child

We check the sum only at leaf nodes because the problem asks for root-to-leaf paths.

If the target sum is 22 and the root node value is 5, what is the new target sum for the children nodes?

A 17

B 22

C 27

D 5

Subtract the root node value (5) from the target sum (22) to get 17 for the children.

What is the time complexity of checking the Path Sum in a binary tree with n nodes?

A O(n)

B O(log n)

C O(n^2)

D O(1)

We may need to visit every node once, so the time complexity is O(n).

Which traversal method is naturally used in the Path Sum problem?

A Breadth-first search

B Level order traversal

C Inorder traversal

D Depth-first search

Depth-first search explores each path from root to leaf, which fits the problem.

Explain how you would solve the Path Sum Root to Leaf problem using recursion.

Think about how to reduce the problem size at each step.

Describe what a root-to-leaf path means and why it matters in the Path Sum problem.

Focus on the start and end points of the path.

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