Path Sum III (Any Path)

▶

Steps

setup

Initialize prefix_counts and stack

Initialize prefix_counts with {0:1} to count empty path sum and start stack with root node (10) and current_sum 0, visited flag False.

💡 Starting prefix_counts with 0:1 allows counting paths that start exactly at the root node.

Line:

prefix_counts = {0: 1}
result = 0
stack = [(root, 0, False)]

💡 Prefix sum zero is counted once initially to handle paths starting at the root.

traverse

Pop root node (10), first visit

Pop node 10 from stack, not visited yet. Add node's value to current_sum (0 + 10 = 10).

💡 Adding node's value updates the prefix sum along the current path.

Line:

node, current_sum, visited = stack.pop()
if not visited:
    current_sum += node.val

💡 Current prefix sum is now 10, representing sum from root to this node.

compare

Check prefix_counts for (current_sum - targetSum) = 2

Look up prefix_counts for key 2 (10 - 8) to find how many paths ending here sum to targetSum.

💡 If prefix_counts has 2, it means a previous prefix sum allows a path summing to targetSum ending at current node.

Line:

result += prefix_counts.get(current_sum - targetSum, 0)

💡 No valid path ends at node 10 alone that sums to 8.

insert

Insert current_sum 10 into prefix_counts

Increment count of prefix sum 10 in prefix_counts from 0 to 1.

💡 Tracking prefix sums allows detecting future paths that use this sum as a base.

Line:

prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1

💡 prefix_counts now includes 10:1, representing one path with sum 10.

expand

Push node 10 back as visited and push right child (-3)

Push node 10 with visited=True to stack for backtracking later. Push right child (-3) with current_sum 10, visited=False.

💡 Marking node visited allows decrementing prefix_counts after children processed.

Line:

stack.append((node, current_sum, True))
if node.right:
    stack.append((node.right, current_sum, False))

💡 Stack now contains nodes to explore next, preserving traversal order.

expand

Push left child (5) of node 10

Push left child (5) with current_sum 10, visited=False onto stack to explore left subtree next.

💡 Left child is pushed last so it is processed first (stack LIFO).

Line:

if node.left:
    stack.append((node.left, current_sum, False))

💡 Stack order ensures DFS explores left subtree before right.

traverse

Pop node 5, first visit, update current_sum to 15

Pop node 5, add its value to current_sum (10 + 5 = 15).

💡 Update prefix sum to reflect path sum from root to node 5.

Line:

if not visited:
    current_sum += node.val

💡 Current prefix sum is 15 at node 5.

compare

Check prefix_counts for key 7 (15 - 8)

Look up prefix_counts for 7 to find valid paths ending at node 5.

💡 No entry for 7 means no valid path ends here summing to targetSum.

Line:

result += prefix_counts.get(current_sum - targetSum, 0)

💡 No new path found ending at node 5.

insert

Insert current_sum 15 into prefix_counts

Increment count of prefix sum 15 from 0 to 1.

💡 Tracking prefix sums allows detecting future valid paths using this sum.

Line:

prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1

💡 prefix_counts now includes 15:1.

expand

Push node 5 back as visited and push right child (2)

Push node 5 with visited=True for backtracking. Push right child (2) with current_sum 15, visited=False.

💡 Backtracking will decrement prefix_counts after children processed.

Line:

stack.append((node, current_sum, True))
if node.right:
    stack.append((node.right, current_sum, False))

💡 Stack updated to explore right child 2 next.

expand

Push left child (3) of node 5

Push left child (3) with current_sum 15, visited=False onto stack to explore left subtree first.

💡 DFS explores left subtree before right due to stack order.

Line:

if node.left:
    stack.append((node.left, current_sum, False))

💡 Stack now has left child 3 on top to process next.

traverse

Pop node 3, first visit, update current_sum to 18

Pop node 3, add its value to current_sum (15 + 3 = 18).

💡 Update prefix sum to reflect path sum from root to node 3.

Line:

if not visited:
    current_sum += node.val

💡 Current prefix sum is 18 at node 3.

compare

Check prefix_counts for key 10 (18 - 8)

Look up prefix_counts for 10 to find valid paths ending at node 3.

💡 Entry for 10 found with count 1, so one new path found ending here.

Line:

result += prefix_counts.get(current_sum - targetSum, 0)

💡 Path 5->3 sums to 8, counted here.

insert

Insert current_sum 18 into prefix_counts

Increment count of prefix sum 18 from 0 to 1.

💡 Tracking prefix sums allows detecting future valid paths using this sum.

Line:

prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1

💡 prefix_counts now includes 18:1.

expand

Push node 3 back as visited and push right child (null)

Push node 3 with visited=True for backtracking. Node 3 has no right child, so no push.

💡 Backtracking will decrement prefix_counts after children processed.

Line:

stack.append((node, current_sum, True))
if node.right:
    stack.append((node.right, current_sum, False))

💡 Stack updated to explore left child (3) next.

expand

Push left child (3) of node 3

Push left child (3) with current_sum 18, visited=False onto stack to explore next.

💡 DFS explores left subtree first.

Line:

if node.left:
    stack.append((node.left, current_sum, False))

💡 Stack now has node 3 (left child) on top.

traverse

Pop node 3 (left child), first visit, update current_sum to 21

Pop node 3, add its value to current_sum (18 + 3 = 21).

💡 Update prefix sum to reflect path sum from root to this node.

Line:

if not visited:
    current_sum += node.val

💡 Current prefix sum is 21 at this node.

compare

Check prefix_counts for key 13 (21 - 8)

Look up prefix_counts for 13 to find valid paths ending at this node.

💡 No entry for 13 means no valid path ends here summing to targetSum.

Line:

result += prefix_counts.get(current_sum - targetSum, 0)

💡 No new path found ending at this node.

insert

Insert current_sum 21 into prefix_counts

Increment count of prefix sum 21 from 0 to 1.

💡 Tracking prefix sums allows detecting future valid paths using this sum.

Line:

prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1

💡 prefix_counts now includes 21:1.

shrink

Backtrack from node 3 (left child), decrement prefix_counts[21]

Node 3 visited again (visited=True), decrement prefix_counts[21] from 1 to 0 to backtrack.

💡 Backtracking removes prefix sums from current path to avoid counting invalid paths.

Line:

else:
    prefix_counts[current_sum] -= 1

💡 Prefix sum 21 no longer counts after leaving this node.

reconstruct

Final step: Return result 3 after full traversal

After fully traversing the tree and backtracking, return the total count of valid paths found, which is 3.

💡 The result accumulates all valid paths found during traversal.

Line:

return result

💡 The algorithm correctly counted all paths summing to targetSum.

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

class Solution:
    def pathSum(self, root, targetSum):
        if not root:
            return 0
        prefix_counts = {0: 1}  # STEP 1
        result = 0
        stack = [(root, 0, False)]  # STEP 1

        while stack:
            node, current_sum, visited = stack.pop()  # STEP 2,7,12,17
            if node is None:
                continue
            if not visited:
                current_sum += node.val  # STEP 2,7,12,17
                result += prefix_counts.get(current_sum - targetSum, 0)  # STEP 3,8,13,18
                prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1  # STEP 4,9,14,19
                stack.append((node, current_sum, True))  # STEP 5,10,15,20
                if node.right:
                    stack.append((node.right, current_sum, False))  # STEP 5,10,15
                if node.left:
                    stack.append((node.left, current_sum, False))  # STEP 6,11,16
            else:
                prefix_counts[current_sum] -= 1  # STEP 20

        return result  # STEP 21

📊

Path Sum III (Any Path) - Watch the Algorithm Execute, Step by Step

Watching each step reveals how prefix sums help efficiently find paths summing to the target without re-exploring all subpaths repeatedly.

insert

0→1

Result: 0

check

Lookup: 2→ 0

0→1

Result: 0

lookup

Lookup: 2→ 0

0→1

Result: 0

insert

0→1

10→1

Result: 0

check

0→1

10→1

Result: 0

check

0→1

10→1

Result: 0

check

Lookup: 7→ 0

0→1

10→1

Result: 0

lookup

Lookup: 7→ 0

0→1

10→1

Result: 0

insert

0→1

10→1

15→1

Result: 0

check

0→1

10→1

15→1

Result: 0

check

0→1

10→1

15→1

Result: 0

check

Lookup: 10→ 1

0→1

10→1lookup

15→1

Result: 0

lookup

Lookup: 10→ 1

0→1

10→1lookup

15→1

Result: 1

insert

0→1

10→1

15→1

18→1

Result: 1

check

0→1

10→1

15→1

18→1

Result: 1

check

0→1

10→1

15→1

18→1

Result: 1

check

Lookup: 13→ 0

0→1

10→1

15→1

18→1

Result: 1

lookup

Lookup: 13→ 0

0→1

10→1

15→1

18→1

Result: 1

insert

0→1

10→1

15→1

18→1

21→1

Result: 1

delete

0→1

10→1

15→1

18→1

21→0

Result: 1

check

0→1

10→0

15→0

18→0

21→0

Result: 3

Key Takeaways

✓ Prefix sums allow counting paths summing to target efficiently without exploring all subpaths explicitly.

This insight is hard to see from code alone because prefix sums abstract away many path details.

✓ Backtracking by decrementing prefix sum counts ensures only valid paths on the current DFS path are counted.

Without backtracking, counts would accumulate incorrectly, leading to overcounting.

✓ The stack's visited flag enables simulating recursion iteratively and controlling when to add or remove prefix sums.

This control flow is subtle and critical to correctly managing prefix sums during traversal.

Practice

1. You need to output the values of a binary tree's nodes in the order: left subtree, node itself, then right subtree, without modifying the tree structure or using extra space proportional to the tree height. Which approach best fits this requirement?

easy

A. Use a breadth-first search (BFS) to visit nodes level by level.

B. Use a recursive preorder traversal that visits root, left, then right nodes.

C. Use Morris traversal to perform inorder traversal with O(1) extra space by temporarily modifying tree links.

D. Use a dynamic programming approach to store and reuse subtree results.

Solution

1. Step 1: Understand traversal order requirement

   Inorder traversal visits left subtree, then node, then right subtree, matching the problem's order.

2. Step 2: Identify approach with O(1) space

   Morris traversal achieves inorder traversal without recursion or stack by temporarily modifying tree pointers, restoring them after use.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Morris traversal is known for O(1) space inorder traversal [OK]

Hint: Morris traversal enables inorder with O(1) space [OK]

Common Mistakes:

• Confusing preorder with inorder traversal order
• Assuming BFS can produce inorder sequence
• Thinking DP applies to traversal order

2. You are given two arrays representing the inorder and postorder traversal sequences of a binary tree. Which approach guarantees reconstructing the original tree efficiently without redundant searches?

easy

A. Use a greedy approach by always attaching nodes as left children when possible.

B. Use dynamic programming to store subtrees and avoid recomputation.

C. Use recursion with a hash map to quickly find root indices in the inorder array.

D. Use breadth-first search to reconstruct the tree level by level.

Solution

1. Step 1: Understand the problem constraints

   Reconstructing a tree from inorder and postorder requires identifying root nodes and splitting subtrees efficiently.

2. Step 2: Evaluate approaches

   Recursion with a hash map allows O(1) root index lookup in inorder, avoiding repeated linear searches and ensuring O(n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Hash map lookup avoids O(n) search per recursion [OK]

Hint: Hash map lookup avoids repeated linear searches [OK]

Common Mistakes:

• Assuming greedy or BFS can reconstruct tree uniquely
• Confusing DP with tree construction
• Ignoring index lookup cost

3. You are given a binary tree and two nodes within it. You need to find the node that is the deepest common ancestor of both nodes. Which approach guarantees an optimal solution in terms of time and space complexity?

easy

A. Use a brute force approach by finding paths from root to each node and then comparing the paths.

B. Build a parent pointer map for all nodes, then use ancestor sets to find the lowest common ancestor.

C. Apply a greedy algorithm that picks the first common node found during a preorder traversal.

D. Use dynamic programming to store results of subtrees and combine them to find the ancestor.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the lowest common ancestor efficiently, ideally in O(n) time and O(n) space.

2. Step 2: Evaluate approaches

   Brute force (A) is correct but less optimal. Greedy (C) fails because it may pick incorrect ancestors. DP (D) is not applicable here. Building parent pointers and using ancestor sets (B) provides an optimal and clean solution.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Parent pointer + ancestor set approach is standard optimal solution [OK]

Hint: Parent pointers + ancestor sets yield optimal LCA solution [OK]

Common Mistakes:

• Assuming greedy traversal finds correct LCA
• Using DP where not applicable
• Brute force is optimal

4. You are given a binary tree and a target sum. The task is to find all root-to-leaf paths where the sum of the node values equals the target sum. Which algorithmic approach guarantees finding all such paths efficiently?

easy

A. Greedy traversal choosing the child with the closest value to the remaining sum

B. Depth-first search (DFS) with path tracking and backtracking to explore all root-to-leaf paths

C. Dynamic programming to store sums at each node and combine results bottom-up

D. Breadth-first search (BFS) with queue to find the shortest path matching the sum

Solution

1. Step 1: Understand problem requires all root-to-leaf paths

   Since we must find all paths, not just one, exhaustive exploration is needed.

2. Step 2: Identify DFS with path tracking and backtracking

   DFS explores each path fully, tracking the current path and sum, backtracking to explore alternatives.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DFS explores all paths, greedy or BFS do not guarantee all paths [OK]

Hint: All root-to-leaf paths require exhaustive DFS [OK]

Common Mistakes:

• Thinking greedy or BFS finds all paths
• Confusing DP for path enumeration

5. Consider this modified code snippet for the Binary Tree Cameras problem. Which line contains the subtle bug that causes incorrect camera placement?

medium

A. Line returning COVERED_NO_CAM after placing a camera instead of HAS_CAM

B. Line returning NOT_COVERED at the end of dfs

C. Line checking if dfs(root) == NOT_COVERED after traversal

D. Line returning COVERED_NO_CAM when node is null

Solution

1. Step 1: Identify camera placement logic

   When a child is NOT_COVERED, a camera must be placed at current node and dfs must return HAS_CAM to indicate camera presence.

2. Step 2: Locate incorrect return

   The code returns COVERED_NO_CAM after placing a camera, which falsely signals no camera here, causing parents to misinterpret coverage.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Returning HAS_CAM is essential after placing a camera [OK]

Hint: Return HAS_CAM after placing camera to signal coverage [OK]

Common Mistakes:

• Returning COVERED_NO_CAM instead of HAS_CAM after camera placement
• Forgetting to add camera if root uncovered
• Mixing coverage states in conditions