Path Sum

▶

Steps

setup

Start DFS at root node 5 with current sum 0

The algorithm begins by calling dfs on the root node (value 5) with an initial current sum of 0.

💡 This initializes the recursion and sets the starting point for accumulating sums along paths.

Line:

return dfs(root, 0)

💡 The root node is the entry point for the DFS traversal.

fill_cells

Add node 5's value to current sum

At node 5, add its value (5) to the current sum (0), updating current sum to 5.

💡 Updating the sum is essential to track the path's total as we go deeper.

Line:

curr_sum += node.val

💡 The current sum now reflects the path sum from root to this node.

traverse

Recurse into left child node 4

The algorithm calls dfs on node 4 (left child of 5) with current sum 5.

💡 Exploring left subtree first follows DFS order and accumulates sums along this path.

Line:

return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)

💡 The recursion stack grows as we go deeper into the left subtree.

fill_cells

Add node 4's value to current sum

At node 4, add its value (4) to current sum (5), updating current sum to 9.

💡 Updating the sum continues to track the total along the current path.

Line:

curr_sum += node.val

💡 The sum now reflects the path 5->4.

traverse

Recurse into left child node 11

The algorithm calls dfs on node 11 (left child of 4) with current sum 9.

💡 Continuing down the left subtree to explore deeper paths.

Line:

return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)

💡 The recursion stack deepens as we explore this path.

fill_cells

Add node 11's value to current sum

At node 11, add its value (11) to current sum (9), updating current sum to 20.

💡 Sum accumulation continues as we go deeper into the path.

Line:

curr_sum += node.val

💡 The sum now reflects the path 5->4->11.

traverse

Recurse into left child node 7 (leaf)

The algorithm calls dfs on node 7 (left child of 11) with current sum 20.

💡 Exploring the left leaf node to check if path sum matches target.

Line:

return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)

💡 We are now at a leaf node candidate for path sum check.

compare

Add node 7's value to current sum and check leaf condition

At leaf node 7, add its value (7) to current sum (20), total 27. Check if 27 equals target 22; it does not.

💡 Leaf nodes are where we check if the path sum matches the target.

Line:

if not node.left and not node.right:
    return curr_sum == targetSum

💡 This path does not satisfy the target sum condition.

traverse

Backtrack and recurse into right child node 2

Since left leaf path failed, backtrack to node 11 and recurse into its right child node 2 with current sum 20.

💡 Backtracking allows exploring alternative paths when one fails.

Line:

return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)

💡 The algorithm explores all possible paths until one matches the target sum.

compare

Add node 2's value to current sum and check leaf condition

At leaf node 2, add its value (2) to current sum (20), total 22. Check if 22 equals target 22; it does.

💡 Finding a leaf node where the path sum matches the target means success.

Line:

if not node.left and not node.right:
    return curr_sum == targetSum

💡 The algorithm finds a valid path and returns True immediately.

returning

Return True up the call stack to root

The True result propagates back through the call stack, returning True at each level without exploring other branches.

💡 Early stopping avoids unnecessary exploration once a valid path is found.

Line:

return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)

💡 The algorithm efficiently stops searching after success.

from typing import Optional

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

def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    def dfs(node, curr_sum):
        if not node:
            return False  # STEP 1: Null node returns False
        curr_sum += node.val  # STEP 2: Add node value to current sum
        if not node.left and not node.right:  # STEP 3: Check leaf node
            return curr_sum == targetSum  # STEP 4: Return True if sum matches
        # STEP 5: Recurse left subtree
        left_result = dfs(node.left, curr_sum)
        if left_result:
            return True  # STEP 6: Early return if left subtree has path
        # STEP 7: Recurse right subtree
        right_result = dfs(node.right, curr_sum)
        return right_result  # STEP 8: Return right subtree result
    return dfs(root, 0)  # STEP 9: Start DFS from root with sum 0

📊

Path Sum - Watch the Algorithm Execute, Step by Step

Watching the algorithm step through each node and decision reveals how early stopping works and how the recursion stack evolves, making the path sum logic crystal clear.

Current node: 1

54811721341

DFS Stack

1 (entered)curr_sum=0

Current node: 1

54811721341

DFS Stack

1 (entered)curr_sum=5

Current node: 2

54811721341

DFS Stack

2 (entered)curr_sum=51 (left_done)curr_sum=5

Current node: 2

54811721341

DFS Stack

2 (entered)curr_sum=91 (left_done)curr_sum=5

Current node: 4

54811721341

DFS Stack

4 (entered)curr_sum=92 (left_done)curr_sum=91 (left_done)curr_sum=5

Current node: 4

54811721341

DFS Stack

4 (entered)curr_sum=202 (left_done)curr_sum=91 (left_done)curr_sum=5

Current node: 5

54811721341

DFS Stack

5 (entered)curr_sum=204 (left_done)curr_sum=202 (left_done)curr_sum=91 (left_done)curr_sum=5

Current node: 5

54811721341

DFS Stack

5 (returning)curr_sum=274 (left_done)curr_sum=202 (left_done)curr_sum=91 (left_done)curr_sum=5

Return: false

Current node: 6

54811721341

DFS Stack

6 (entered)curr_sum=204 (right_done)curr_sum=202 (left_done)curr_sum=91 (left_done)curr_sum=5

Current node: 6

54811721341

DFS Stack

6 (returning)curr_sum=224 (returning)curr_sum=222 (left_done)curr_sum=91 (left_done)curr_sum=5

Return: true

Current node: 1

54811721341

Return: true

Key Takeaways

✓ DFS explores each root-to-leaf path accumulating sums to check for target sum.

This insight is hard to see from code alone because recursion hides the path exploration order.

✓ Early stopping returns true immediately when a valid path is found, avoiding unnecessary work.

Visualizing the call stack and return values clarifies how early stopping improves efficiency.

✓ Backtracking occurs when a path fails, and the algorithm explores alternative branches systematically.

Seeing the recursion unwind and try other branches concretely shows how all paths are checked.

Practice

1. Consider the following Python code implementing the Morris Preorder Traversal approach to sum root-to-leaf numbers. Given the binary tree: 1 / \ 2 3 What is the final value of the variable total returned by sumNumbers?

easy

A. 5

B. 15

C. 25

D. 26

Solution

1. Step 1: Trace path 1->2

   current_number accumulates 1 then 12; leaf node 2 adds 12 to total.

2. Step 2: Trace path 1->3

   current_number resets to 1, then accumulates 13; leaf node 3 adds 13 to total. Total = 12 + 13 = 25.

3. Step 3: Check for off-by-one or missed increments

   Integer division after visiting left subtree correctly adjusts current_number; no extra addition occurs.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Sum of 12 and 13 is 25, matching code behavior [OK]

Hint: Trace current_number updates carefully at each node [OK]

Common Mistakes:

• Off-by-one in current_number division
• Adding non-leaf nodes to total

2. What is the time complexity of the optimal DFS with two-value return solution for the House Robber III problem on a tree with n nodes?

medium

A. O(n^2) due to checking grandchildren nodes explicitly

B. O(n) but with extra O(n) space for memoization arrays

C. O(n) because each node is visited once in DFS

D. O(n log n) because of recursive calls and combining results

Solution

1. Step 1: Identify DFS traversal cost

   The algorithm visits each node exactly once in a postorder DFS traversal.

2. Step 2: Analyze operations per node

   At each node, constant time operations are done: combining left and right child results, no repeated work.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear traversal of n nodes -> O(n) time [OK]

Hint: DFS visits each node once, no repeated subproblems [OK]

Common Mistakes:

• Assuming O(n^2) due to grandchildren checks
• Confusing recursion stack space with time complexity

3. The following code attempts to find the Lowest Common Ancestor using parent pointers. Identify the line containing the subtle bug that causes incorrect results when one node is ancestor of the other.

def lowestCommonAncestor(root, p, q):
    parent = {root: None}
    stack = [root]
    while p not in parent or q not in parent:
        node = stack.pop()
        if node.left:
            parent[node.left] = node
            stack.append(node.left)
        if node.right:
            parent[node.right] = node
            stack.append(node.right)

    ancestors = set()
    while p:
        ancestors.add(p)
        p = parent[p]
    while q not in ancestors:
        q = parent[q]
    return q

medium

A. Line: while p not in parent or q not in parent:

B. Line: while p:

C. Line: while q not in ancestors:

D. Line: parent = {root: None}

Solution

1. Step 1: Analyze parent map construction loop

   The loop 'while p not in parent or q not in parent:' ensures both nodes are in the parent map before ancestor sets are built.

2. Step 2: Identify subtle bug

   If one node is ancestor of the other, the loop may terminate prematurely if only one node is in parent map, causing KeyError later.

3. Step 3: Explanation

   The bug is that the loop condition does not guarantee both nodes are fully processed in the parent map before ancestor traversal.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Loop condition must ensure both nodes are in parent map to avoid errors [OK]

Hint: Parent map construction loop must fully process both nodes [OK]

Common Mistakes:

• Assuming parent map always complete
• Ignoring incomplete parent map causing KeyError
• Misplacing bug in ancestor set loops

4. What is the time complexity of the BFS-based serialization and deserialization of a binary tree with n nodes, assuming the tree is balanced? Consider both serialization and deserialization separately.

medium

A. Serialization: O(n log n), Deserialization: O(n log n)

B. Serialization: O(n), Deserialization: O(n^2)

C. Serialization: O(n), Deserialization: O(n)

D. Serialization: O(n^2), Deserialization: O(n)

Solution

1. Step 1: Analyze serialization time

   Each node is enqueued and dequeued exactly once, so serialization is O(n).

2. Step 2: Analyze deserialization time

   Deserialization processes each node once, reconstructing the tree in O(n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Both serialization and deserialization scale linearly with number of nodes [OK]

Hint: Each node is processed once in BFS serialization/deserialization [OK]

Common Mistakes:

• Assuming deserialization is O(n^2) due to nested loops
• Confusing tree height with number of nodes
• Thinking serialization is O(n log n) due to queue operations

5. Consider the following buggy deserialization code snippet for BFS-based tree reconstruction. Which line contains the subtle bug that causes incorrect tree structure when deserializing?

def deserialize(data):
    if not data:
        return None
    vals = data.split(',')
    root = TreeNode(int(vals[0]))
    queue = deque([root])
    i = 1
    while queue:
        node = queue.popleft()
        if vals[i] != 'X':
            node.left = TreeNode(int(vals[i]))
            queue.append(node.left)
        i += 1
        if vals[i] != 'X':
            node.right = TreeNode(int(vals[i]))
            queue.append(node.right)
        i += 1
    return root

medium

A. Line: if vals[i] != 'X': (left child check)

B. Line: i += 1 (after left child assignment)

C. Line: if vals[i] != 'X': (right child check)

D. Line: while queue: (loop condition)

Solution

1. Step 1: Identify potential infinite loop

   The loop condition 'while queue:' does not check if 'i' has exceeded vals length, risking index out of range or infinite loop.

2. Step 2: Understand impact on deserialization

   Without checking 'i < len(vals)', the loop may continue after all nodes processed, causing errors or incorrect tree structure.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Loop condition must ensure 'i' stays within bounds to avoid deserialization bugs [OK]

Hint: Loop must check index bounds to avoid infinite loops [OK]

Common Mistakes:

• Not checking index bounds in deserialization loops
• Mixing up left and right child assignments
• Forgetting to append children to queue