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. Given the following Morris inorder traversal code, what is the final output list after running inorderTraversal on this tree?

Tree structure:
2
/ \ 1 3

from typing import Optional, List

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

def inorderTraversal(root: Optional[TreeNode]) -> List[int]:
    result = []
    current = root
    while current:
        if not current.left:
            result.append(current.val)  # visit node
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if not predecessor.right:
                predecessor.right = current  # create thread
                current = current.left
            else:
                predecessor.right = None  # remove thread
                result.append(current.val)  # visit node
                current = current.right
    return result

easy

A. [1, 2, 3]

B. [1, 3, 2]

C. [2, 1, 3]

D. [3, 2, 1]

Solution

1. Step 1: Trace traversal starting at root=2

   Current=2 has left child 1, find predecessor in left subtree: node 1 (no right child). Create thread from 1.right to 2, move current to 1.

2. Step 2: Visit node 1 (no left child), append 1, move current to 1.right which points to 2 (thread).

   Remove thread, append 2, move current to 2.right=3. Node 3 has no left child, append 3, move current to null.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Inorder traversal of tree 1,2,3 is [1,2,3] [OK]

Hint: Inorder traversal visits left, root, right [OK]

Common Mistakes:

• Appending before removing thread
• Visiting root before left subtree
• Confusing preorder with inorder output

2. You are given a binary tree and need to find the longest path from the root node down to the farthest leaf node. Which algorithmic approach guarantees an optimal solution to determine this maximum depth?

easy

A. Dynamic Programming with memoization on node values

B. Greedy traversal picking the first child node at each step

C. Depth-First Search (DFS) or Breadth-First Search (BFS) to explore all nodes

D. Sorting nodes by value and selecting the deepest node

Solution

1. Step 1: Understand the problem requires exploring all paths from root to leaves

   Finding maximum depth means checking every path from root to leaves, so partial or greedy approaches won't guarantee correctness.

2. Step 2: Identify algorithms that explore all nodes

   DFS or BFS traverse all nodes systematically, ensuring the maximum depth is found. Greedy or sorting approaches do not consider all paths.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DFS and BFS both visit all nodes to find max depth [OK]

Hint: Max depth requires full traversal, not greedy or sorting [OK]

Common Mistakes:

• Assuming greedy traversal finds max depth
• Confusing max depth with max node value
• Thinking sorting nodes helps depth calculation

3. What is the time complexity of the optimized recursive solution that uses a hash map for index lookup when constructing a binary tree from inorder and postorder traversals of size n?

medium

A. O(n) because each node is processed once and index lookup is O(1)

B. O(n^2) due to repeated slicing of arrays

C. O(n log n) because of balanced tree recursion depth

D. O(n) but with O(n) auxiliary space for recursion stack and hash map

Solution

1. Step 1: Analyze time complexity

   Using a hash map avoids repeated linear searches, so each node is processed once -> O(n) time.

2. Step 2: Analyze space complexity

   Hash map stores n elements, recursion stack can be up to O(n) in skewed trees, so total auxiliary space is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Time is O(n), space includes recursion stack and hash map [OK]

Hint: Hash map reduces search to O(1), recursion stack adds O(n) space [OK]

Common Mistakes:

• Assuming slicing causes O(n^2) time
• Ignoring recursion stack space
• Confusing balanced tree depth with complexity

4. What is the space complexity of the optimal in-place flatten algorithm that uses reverse preorder traversal with a global pointer on a binary tree of n nodes and height h?

medium

A. O(n) due to storing all nodes in a list during traversal

B. O(1) because the algorithm modifies the tree in-place without extra memory

C. O(log n) because the tree height is always balanced and recursion stack is limited

D. O(h) due to recursion stack depth in worst case of skewed tree

Solution

1. Step 1: Identify auxiliary space usage

   The algorithm uses recursion, so space is dominated by recursion stack depth, which is the tree height h.

2. Step 2: Clarify why O(h) not O(1) or O(n)

   It does not store nodes externally (not O(n)) and is not constant space due to recursion stack (not O(1)). For skewed trees, h can be up to n.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Recursion stack space equals tree height h [OK]

Hint: Recursion stack space equals tree height h [OK]

Common Mistakes:

• Assuming O(1) space because of in-place modification
• Confusing recursion stack with explicit data structures
• Assuming balanced tree always so O(log n) space

5. If the problem is modified so that the postorder traversal may contain duplicate values, which of the following changes is necessary to correctly reconstruct the tree?

hard

A. Modify the algorithm to store indices of all occurrences of each value in inorder and track usage to avoid ambiguity.

B. Use a hash map from value to index in inorder traversal as before, ignoring duplicates.

C. Switch to preorder and inorder traversals which do not have duplicates.

D. Use a greedy approach attaching nodes as left children to handle duplicates.

Solution

1. Step 1: Understand the impact of duplicates

   Duplicates break the uniqueness of value-to-index mapping in inorder traversal, so a simple hash map is insufficient.

2. Step 2: Required modification

   Store all indices of each value in inorder and track which occurrence is used to correctly split subtrees and avoid ambiguity.

3. Step 3: Why other options fail

   Ignoring duplicates or switching traversals does not solve ambiguity; greedy approach fails to reconstruct correct structure.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Tracking multiple indices per value is necessary for duplicates [OK]

Hint: Duplicates require tracking all indices, not just one [OK]

Common Mistakes:

• Ignoring duplicates in hash map
• Assuming unique values always
• Switching traversal types incorrectly