House Robber III (On Tree)

▶

Steps

setup

Initialize DP Table and Start Post-Order Traversal

We start with an empty DP table for all nodes. No DP values are computed yet, so all cells are '?'. The traversal will process nodes from leaves up to the root.

💡 Initialization sets the stage for bottom-up computation, ensuring no values are assumed before processing children.

Line:

def rob(root):
    def dfs(node):
        if not node:
            return (0, 0)

💡 DP values must be computed bottom-up; leaves first, then parents.

fill_cells

Process Leaf Node with Value 3 (Right child of left child)

We reach the leaf node with value 3 (right child of left child). Since it has no children, rob = 3 and not_rob = 0.

💡 Leaf nodes have simple DP values: rob equals node value, not_rob is zero because no children to rob.

Line:

if not node:
    return (0, 0)
left = dfs(node.left)
right = dfs(node.right)

💡 Leaf nodes provide base cases for DP computation.

fill_cells

Process Leaf Node with Value 1 (Right child of right child)

We process the leaf node with value 1 (right child of right child). Its rob value is 1 and not_rob is 0, as it has no children.

💡 Similar to previous leaf, base DP values are straightforward.

Line:

if not node:
    return (0, 0)
left = dfs(node.left)
right = dfs(node.right)

💡 Leaf nodes consistently provide base DP values.

fill_cells

Process Node with Value 2 (Left child)

For node 2, rob = 2 + not_rob of children = 2 + 0 + 0 = 2. not_rob = max(rob, not_rob) of children = max(0,3) = 3.

💡 Combining children's DP values shows how robbing this node excludes robbing children.

Line:

left = dfs(node.left)
right = dfs(node.right)
rob_node = node.val + left[0] + right[0]
not_rob_node = max(left) + max(right)

💡 Robbing a node adds its value plus not robbing children; not robbing node allows robbing or not robbing children for max gain.

fill_cells

Process Node with Value 3 (Right child)

For node 3 (right child), rob = 3 + not_rob of children = 3 + 0 + 0 = 3. not_rob = max(rob, not_rob) of children = max(0,1) = 1.

💡 Same logic applies: robbing node excludes robbing children, not robbing node allows max of children.

Line:

left = dfs(node.left)
right = dfs(node.right)
rob_node = node.val + left[0] + right[0]
not_rob_node = max(left) + max(right)

💡 DP values reflect the best choice at this subtree.

fill_cells

Process Root Node with Value 3

For root node 3, rob = 3 + not_rob of children = 3 + 3 + 1 = 7. not_rob = max(rob, not_rob) of children = 3 + 3 = 6.

💡 Combining children's DP values at root shows maximum money robbable without alerting police.

Line:

rob_node = node.val + left[0] + right[0]
not_rob_node = max(left) + max(right)
return (not_rob_node, rob_node)

💡 The root's DP values summarize the entire tree's optimal robbery plan.

compare

Compare rob and not_rob at Root to Find Final Answer

We compare rob (7) and not_rob (6) at the root. Since 7 > 6, the maximum amount robbed is 7.

💡 The final answer is the maximum of rob and not_rob at the root node.

Line:

return max(dfs(root))

💡 The final decision is made by comparing the two DP states at the root.

reconstruct

Summary: Robbing Nodes 3 (root), 3 (right child of left child), and 1 (right child of right child)

The optimal solution includes robbing the root (3), the right child of the left child (3), and the right child of the right child (1), totaling 7.

💡 This step connects DP values to actual nodes robbed, clarifying the solution.

Line:

# Reconstruction is conceptual here; no explicit code

💡 DP values encode which nodes to rob to maximize money without robbing adjacent nodes.

fill_cells

Confirm DP Table Fully Computed

All nodes have their DP values computed, no '?' remain. The table fully represents the solution space.

💡 Complete DP table ensures no missing computations and correctness of the solution.

Line:

return max(dfs(root))

💡 DP table completeness is essential for correctness and final answer extraction.

finalize

Final Step: Return Maximum Robbed Amount

The algorithm returns 7, the maximum amount that can be robbed from the tree without alerting the police.

💡 Returning the max of rob and not_rob at root completes the algorithm.

Line:

return max(dfs(root))

💡 The final returned value is the solution to the problem.

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

def rob(root):
    def dfs(node):
        if not node:  # STEP 1
            return (0, 0)  # (not_rob, rob)
        left = dfs(node.left)  # STEP 2-5
        right = dfs(node.right)
        rob_node = node.val + left[0] + right[0]  # STEP 4
        not_rob_node = max(left) + max(right)  # STEP 4
        return (not_rob_node, rob_node)  # STEP 6
    return max(dfs(root))  # STEP 7

📊

House Robber III (On Tree) - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how the tree structure influences the DP decisions and why robbing adjacent nodes is forbidden.

Initializing dp array

i\w	0	1
i=0	?	?
i=1	?	?
i=2	?	?
i=3	?	?
i=4	?	?

uncomputed

Item 3 - wt:0 val:3

i\w	0	1
i=0	?	?
i=1	?	?
i=2	?	?
i=3	0	3
i=4	?	?

leaf node computed

Item 4 - wt:0 val:1

i\w	0	1
i=0	?	?
i=1	?	?
i=2	?	?
i=3	0	3
i=4	0	1

leaf node computed

Item 1 - wt:0 val:2

i\w	0	1
i=0	?	?
i=1	3	2
i=2	?	?
i=3	0	3
i=4	0	1

node computed

Item 2 - wt:0 val:3

i\w	0	1
i=0	?	?
i=1	3	2
i=2	1	3
i=3	0	3
i=4	0	1

node computed

Item 0 - wt:0 val:3

i\w	0	1
i=0	6	7
i=1	3	2
i=2	1	3
i=3	0	3
i=4	0	1

root computed

Item 0 - wt:0 val:7

i\w	0	1
i=0	6	7
i=1	3	2
i=2	1	3
i=3	0	3
i=4	0	1

final answer

Item 0 - wt:0 val:7

i\w	0	1
i=0	6	7
i=1	3	2
i=2	1	3
i=3	0	3
i=4	0	1

robbed root

Initializing dp array

i\w	0	1
i=0	6	7
i=1	3	2
i=2	1	3
i=3	0	3
i=4	0	1

computed

Item 0 - wt:0 val:7

i\w	0	1
i=0	6	7
i=1	3	2
i=2	1	3
i=3	0	3
i=4	0	1

answer cell

Key Takeaways

✓ DP on trees requires bottom-up post-order traversal to ensure children are processed before parents.

This traversal order is crucial because parent's DP values depend on children's results, which is not obvious from code alone.

✓ Each node stores two DP states: rob and not_rob, representing mutually exclusive choices.

Understanding these two states clarifies why we cannot rob adjacent nodes and how the algorithm enforces this constraint.

✓ The final answer is the max of rob and not_rob at the root, reflecting the best overall choice.

Seeing the final comparison visually helps students grasp how the DP values translate to the solution.

Practice

1. You need to visit all nodes of a binary tree in the order: root node first, then recursively the left subtree, followed by the right subtree. Which algorithmic approach guarantees this traversal order efficiently without extra space for recursion or stack?

easy

A. Postorder traversal using two stacks

B. Level-order traversal using a queue

C. Morris preorder traversal using threaded binary tree

D. Inorder traversal using recursion

Solution

1. Step 1: Understand traversal order requirement

   The problem requires visiting root before left and right subtrees, which is preorder traversal.

2. Step 2: Identify approach with no extra space

   Morris preorder traversal uses threaded binary trees to achieve preorder traversal without recursion or stack, thus optimal in space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Preorder visits root first; Morris traversal achieves this with O(1) space [OK]

Hint: Preorder visits root before children [OK]

Common Mistakes:

• Confusing inorder or postorder with preorder traversal
• Assuming recursion is always needed
• Using level-order which visits nodes by depth

2. Given a binary tree, you need to find the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. Which approach guarantees an optimal solution to this problem?

easy

A. Perform a postorder traversal computing heights and update the diameter at each node using recursion with a global variable.

B. Apply dynamic programming with memoization on node pairs to find longest paths.

C. Use a greedy traversal that always chooses the deeper subtree at each node.

D. Calculate the height of the tree and multiply by two to estimate the diameter.

Solution

1. Step 1: Understand the problem requires the longest path between any two nodes, not necessarily passing through root.

   The diameter can be found by checking the sum of left and right subtree heights at every node.

2. Step 2: Recognize that a postorder traversal with recursion and a global variable to track diameter updates at each node ensures all paths are considered.

   This approach visits each node once, updating the diameter with left_height + right_height.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Postorder traversal with global diameter update covers all nodes [OK]

Hint: Diameter updates at every node, not just root [OK]

Common Mistakes:

• Thinking diameter must pass through root
• Using greedy to pick deeper subtree only
• Confusing diameter with twice height

3. Given a binary tree and a target sum, you need to count all paths where the sum of the node values along the path equals the target. The path can start and end at any node but must go downwards (parent to child). Which approach guarantees an optimal solution in terms of time complexity?

easy

A. Use a brute force DFS starting from every node, checking all downward paths for the target sum.

B. Use dynamic programming to store sums of subtrees and combine results bottom-up.

C. Use a DFS with a prefix sum hash map to track cumulative sums and count valid paths in one traversal.

D. Use a greedy approach to prune paths that exceed the target sum early.

Solution

1. Step 1: Understand problem constraints and path definition

   The path can start and end anywhere but must go downwards, so checking all paths naively is expensive.

2. Step 2: Recognize prefix sum with DFS pattern

   Using a prefix sum hash map during DFS allows counting all valid paths in O(n) time by tracking cumulative sums and their frequencies.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Prefix sum + DFS solves in linear time [OK]

Hint: Prefix sums track cumulative sums efficiently [OK]

Common Mistakes:

• Assuming paths must start at root or leaf
• Using brute force DFS from every node without pruning
• Trying greedy pruning which fails on negative values

4. Suppose the problem changes: the binary tree is no longer complete but only a general binary tree. Which of the following statements about counting nodes efficiently is true?

hard

A. Breadth-first search (BFS) can count nodes in O(log n) time for any binary tree.

B. The optimal binary search approach on the last level still applies with minor modifications.

C. Using tree height to check perfect subtrees can still reduce time complexity to O((log n)^2).

D. A simple DFS traversal counting all nodes is the only guaranteed correct method with O(n) time.

Solution

1. Step 1: Understand the problem change

   The tree is no longer complete, so properties used by optimal methods do not hold.

2. Step 2: Identify correct counting method

   Only a full traversal (DFS or BFS) guarantees counting all nodes correctly in O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Optimal methods rely on completeness, which is lost here [OK]

Hint: Without completeness, must traverse all nodes [OK]

Common Mistakes:

• Trying to apply binary search on last level
• Assuming height checks still reduce complexity

5. Suppose the binary tree nodes have parent pointers already, but the tree is very deep (height h). You want to find the Lowest Common Ancestor of two nodes p and q. Which approach is best to optimize time and space, and why?

hard

A. Use brute force by checking all ancestors of p and q repeatedly until common ancestor is found.

B. Use the parent pointer + ancestor set approach, building a set for p's ancestors and then traversing q's ancestors.

C. Use recursive DFS from root to find paths to p and q, then compare paths to find LCA.

D. Use the parent pointer + two-pointer technique: move the deeper node up until both nodes are at the same depth, then move both up simultaneously until they meet.

Solution

1. Step 1: Understand problem constraints

   Nodes have parent pointers, tree is deep, so space usage matters.

2. Step 2: Evaluate approaches

   Ancestor set approach (B) uses O(h) space. Recursive DFS (C) and brute force (D) are inefficient for deep trees.

3. Step 3: Two-pointer technique

   Moving deeper node up to equalize depth, then moving both up simultaneously uses O(1) space and O(h) time, optimal for deep trees.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Two-pointer approach optimizes space and time for deep trees with parent pointers [OK]

Hint: Two-pointer approach uses O(1) space for LCA with parent pointers [OK]

Common Mistakes:

• Using ancestor sets unnecessarily
• Recursing from root wasting time
• Brute force repeated ancestor checks