Bird
Raised Fist0
Interview Prepdp-advanced-trees-bitmaskmediumAmazonGoogle

House Robber III (On Tree)

Choose your preparation mode4 modes available
🎯
House Robber III (On Tree)
mediumDPAmazonGoogle

Imagine a thief planning to rob houses arranged in a neighborhood shaped like a tree. The thief cannot rob two directly connected houses to avoid alerting the police.

💡 This problem is a classic example of dynamic programming on trees, which can be tricky because unlike arrays, trees have hierarchical structures without linear order. Beginners often struggle to understand how to carry state information up and down the tree and how to avoid recomputation.
📋
Problem Statement

Given a binary tree where each node represents the amount of money stashed in a house, determine the maximum amount of money the thief can rob without robbing two directly connected houses (parent and child). Return the maximum amount of money that can be robbed.

The number of nodes in the tree is in the range [1, 10^5].0 <= Node.val <= 10^4
💡
Example
Input"root = [3,2,3,null,3,null,1]"
Output7

Rob houses with values 3 (root), 3 (right child of left child), and 1 (right child of right child). Total = 3 + 3 + 1 = 7.

Input"root = [3,4,5,1,3,null,1]"
Output9

Rob houses with values 4 and 5. Total = 4 + 5 = 9.

  • Single node tree → output is node's value
  • All nodes have zero value → output is 0
  • Linear tree (like a linked list) → behaves like House Robber I
  • Complete binary tree with equal values → choose alternate levels
🔁
Why DP?
Why greedy fails:

A greedy approach that always picks the current node with the highest value fails because it might force skipping large sums in children or grandchildren. For example, picking a parent with value 10 might prevent robbing two children with values 6 and 7, losing a total of 13.

DP state:

dp[node] = (max_if_not_robbed, max_if_robbed) where max_if_not_robbed is the max money if we do NOT rob this node, and max_if_robbed is the max money if we rob this node.

Recurrence:dp[node].rob = node.val + sum of dp[child].not_rob for all children; dp[node].not_rob = sum of max(dp[child].rob, dp[child].not_rob) for all children

If we rob the current node, we cannot rob its children, so we add node's value plus the max money from not robbing children. If we don't rob the current node, we take the max of robbing or not robbing each child.

⚠️
Common Mistakes
Forgetting to skip children when robbing current node

Incorrectly sums values leading to overcounting and wrong answer

✅ Ensure when robbing current node, add only grandchildren's values, not children

Not caching results in recursion

Exponential time leading to TLE

✅ Use memoization or bottom-up DP to store intermediate results

Mixing up the order of post-order traversal

Computes parent before children, leading to missing data and errors

✅ Always compute children before parent in DP on trees

Using node values as keys in memo without node identity

Incorrect caching leading to wrong results if values repeat

✅ Use node references or unique IDs as keys in memo

🧠
Brute Force (Pure Recursion)
💡 This approach explores all possibilities by deciding for each node whether to rob it or not, without caching results. It is important to understand this to grasp the problem's complexity and why optimization is needed.

Intuition

At each node, we try robbing it and skipping its children, or skipping it and robbing its children, then take the maximum.

Algorithm

  1. Start at the root node.
  2. For each node, recursively compute the max money if we rob it (skip children) and if we don't rob it (consider children).
  3. Return the maximum of robbing or not robbing the root.
  4. Combine results from subtrees to get the final answer.
💡 The recursion tree grows exponentially because each node branches into two choices, making it hard to track without memoization.
Recurrence:f(node) = max(node.val + sum of f(grandchildren), sum of f(children))
</>
Code
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rob(root):
    if not root:
        return 0
    val = root.val
    if root.left:
        val += rob(root.left.left) + rob(root.left.right)
    if root.right:
        val += rob(root.right.left) + rob(root.right.right)
    return max(val, rob(root.left) + rob(root.right))

# Example usage:
# root = TreeNode(3, TreeNode(2, None, TreeNode(3)), TreeNode(3, None, TreeNode(1)))
# print(rob(root))  # Output: 7
Line Notes
if not root:Base case: no house means no money
val = root.valStart with robbing current node's value
if root.left:Add grandchildren's values if left child exists
return max(val, rob(root.left) + rob(root.right))Choose max between robbing current node plus grandchildren or robbing children
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public int rob(TreeNode root) {
        if (root == null) return 0;
        int val = root.val;
        if (root.left != null) {
            val += rob(root.left.left) + rob(root.left.right);
        }
        if (root.right != null) {
            val += rob(root.right.left) + rob(root.right.right);
        }
        return Math.max(val, rob(root.left) + rob(root.right));
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(2);
        root.left.right = new TreeNode(3);
        root.right = new TreeNode(3);
        root.right.right = new TreeNode(1);
        Solution sol = new Solution();
        System.out.println(sol.rob(root)); // Output: 7
    }
}
Line Notes
if (root == null) return 0;Base case: no node means no money
int val = root.val;Start with current node's value
if (root.left != null)Check if left child exists to add grandchildren
return Math.max(val, rob(root.left) + rob(root.right));Choose max between robbing current node plus grandchildren or robbing children
#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int rob(TreeNode* root) {
        if (!root) return 0;
        int val = root->val;
        if (root->left) {
            val += rob(root->left->left) + rob(root->left->right);
        }
        if (root->right) {
            val += rob(root->right->left) + rob(root->right->right);
        }
        return max(val, rob(root->left) + rob(root->right));
    }
};

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(2);
    root->left->right = new TreeNode(3);
    root->right = new TreeNode(3);
    root->right->right = new TreeNode(1);
    Solution sol;
    cout << sol.rob(root) << endl; // Output: 7
    return 0;
}
Line Notes
if (!root) return 0;Base case: no node means no money
int val = root->val;Start with current node's value
if (root->left)Check if left child exists to add grandchildren
return max(val, rob(root->left) + rob(root->right));Choose max between robbing current node plus grandchildren or robbing children
function TreeNode(val, left=null, right=null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function rob(root) {
    if (!root) return 0;
    let val = root.val;
    if (root.left) {
        val += rob(root.left.left) + rob(root.left.right);
    }
    if (root.right) {
        val += rob(root.right.left) + rob(root.right.right);
    }
    return Math.max(val, rob(root.left) + rob(root.right));
}

// Example usage:
// const root = new TreeNode(3, new TreeNode(2, null, new TreeNode(3)), new TreeNode(3, null, new TreeNode(1)));
// console.log(rob(root)); // Output: 7
Line Notes
if (!root) return 0;Base case: no house means no money
let val = root.val;Start with robbing current node's value
if (root.left)Add grandchildren's values if left child exists
return Math.max(val, rob(root.left) + rob(root.right));Choose max between robbing current node plus grandchildren or robbing children
⏱
Complexity
TimeO(2^n)
SpaceO(n) due to recursion stack

Each node branches into two recursive calls for grandchildren and children, leading to exponential calls.

💡 For n=20, this means over a million calls, which is impractical.
Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's structure.

🧠
Top-Down Memoization
💡 Memoization caches results of subproblems to avoid recomputation, drastically improving efficiency while keeping the recursive structure.

Intuition

Store the maximum money for each node once computed, so repeated calls return cached results.

Algorithm

  1. Use a hash map to store results for each node.
  2. For each node, check if result is cached; if yes, return it.
  3. Otherwise, compute max money by robbing or skipping the node recursively.
  4. Cache and return the computed result.
💡 Memoization turns exponential recursion into linear by remembering answers.
Recurrence:f(node) = max(node.val + sum of f(grandchildren), sum of f(children)) with memoization
</>
Code
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rob(root):
    memo = {}
    def dfs(node):
        if not node:
            return 0
        if node in memo:
            return memo[node]
        val = node.val
        if node.left:
            val += dfs(node.left.left) + dfs(node.left.right)
        if node.right:
            val += dfs(node.right.left) + dfs(node.right.right)
        res = max(val, dfs(node.left) + dfs(node.right))
        memo[node] = res
        return res
    return dfs(root)

# Example usage:
# root = TreeNode(3, TreeNode(2, None, TreeNode(3)), TreeNode(3, None, TreeNode(1)))
# print(rob(root))  # Output: 7
Line Notes
memo = {}Initialize cache to store results for nodes
if node in memo:Return cached result if available
val = node.valStart with robbing current node's value
memo[node] = resCache computed result to avoid recomputation
import java.util.HashMap;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    private HashMap<TreeNode, Integer> memo = new HashMap<>();

    public int rob(TreeNode root) {
        if (root == null) return 0;
        if (memo.containsKey(root)) return memo.get(root);
        int val = root.val;
        if (root.left != null) {
            val += rob(root.left.left) + rob(root.left.right);
        }
        if (root.right != null) {
            val += rob(root.right.left) + rob(root.right.right);
        }
        int res = Math.max(val, rob(root.left) + rob(root.right));
        memo.put(root, res);
        return res;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(2);
        root.left.right = new TreeNode(3);
        root.right = new TreeNode(3);
        root.right.right = new TreeNode(1);
        Solution sol = new Solution();
        System.out.println(sol.rob(root)); // Output: 7
    }
}
Line Notes
private HashMap<TreeNode, Integer> memo = new HashMap<>();Cache to store results for nodes
if (memo.containsKey(root)) return memo.get(root);Return cached result if available
int val = root.val;Start with current node's value
memo.put(root, res);Cache computed result to avoid recomputation
#include <iostream>
#include <unordered_map>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

struct TreeNodeHash {
    size_t operator()(const TreeNode* node) const {
        return hash<long long>()((long long)node);
    }
};

class Solution {
    unordered_map<TreeNode*, int, TreeNodeHash> memo;
public:
    int rob(TreeNode* root) {
        if (!root) return 0;
        if (memo.count(root)) return memo[root];
        int val = root->val;
        if (root->left) {
            val += rob(root->left->left) + rob(root->left->right);
        }
        if (root->right) {
            val += rob(root->right->left) + rob(root->right->right);
        }
        int res = max(val, rob(root->left) + rob(root->right));
        memo[root] = res;
        return res;
    }
};

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(2);
    root->left->right = new TreeNode(3);
    root->right = new TreeNode(3);
    root->right->right = new TreeNode(1);
    Solution sol;
    cout << sol.rob(root) << endl; // Output: 7
    return 0;
}
Line Notes
unordered_map<TreeNode*, int, TreeNodeHash> memo;Cache to store results for nodes
if (memo.count(root)) return memo[root];Return cached result if available
int val = root->val;Start with current node's value
memo[root] = res;Cache computed result to avoid recomputation
function TreeNode(val, left=null, right=null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

const memo = new Map();
function rob(root) {
    if (!root) return 0;
    if (memo.has(root)) return memo.get(root);
    let val = root.val;
    if (root.left) {
        val += rob(root.left.left) + rob(root.left.right);
    }
    if (root.right) {
        val += rob(root.right.left) + rob(root.right.right);
    }
    const res = Math.max(val, rob(root.left) + rob(root.right));
    memo.set(root, res);
    return res;
}

// Example usage:
// const root = new TreeNode(3, new TreeNode(2, null, new TreeNode(3)), new TreeNode(3, null, new TreeNode(1)));
// console.log(rob(root)); // Output: 7
Line Notes
const memo = new Map();Cache to store results for nodes
if (memo.has(root)) return memo.get(root);Return cached result if available
let val = root.val;Start with current node's value
memo.set(root, res);Cache computed result to avoid recomputation
⏱
Complexity
TimeO(n)
SpaceO(n) due to recursion stack and memo

Each node is computed once and cached, so linear time.

💡 For n=10^5, this is efficient enough to run within seconds.
Interview Verdict: Accepted

Memoization makes the solution efficient and practical for large inputs.

🧠
Bottom-Up DP with Post-Order Traversal
💡 This approach uses a bottom-up traversal to compute the answer for each node based on its children, avoiding recursion overhead and making the logic clearer.

Intuition

For each node, compute two values: max money if robbed and max money if not robbed, using children's results.

Algorithm

  1. Traverse the tree in post-order (children before parent).
  2. For each node, compute two values: rob and not_rob.
  3. rob = node.val + sum of not_rob from children.
  4. not_rob = sum of max(rob, not_rob) from children.
  5. Return max of rob and not_rob at root.
💡 This approach cleanly separates the two states per node and uses children's results to build parent's answer.
Recurrence:dp[node].rob = node.val + sum(dp[child].not_rob); dp[node].not_rob = sum(max(dp[child].rob, dp[child].not_rob))
</>
Code
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:
            return (0, 0)  # (not_rob, rob)
        left = dfs(node.left)
        right = dfs(node.right)
        rob_node = node.val + left[0] + right[0]
        not_rob_node = max(left) + max(right)
        return (not_rob_node, rob_node)
    return max(dfs(root))

# Example usage:
# root = TreeNode(3, TreeNode(2, None, TreeNode(3)), TreeNode(3, None, TreeNode(1)))
# print(rob(root))  # Output: 7
Line Notes
def dfs(node):Helper function to return tuple (not_rob, rob) for node
if not node:Base case returns zero for both states
rob_node = node.val + left[0] + right[0]Rob current node plus not robbing children
not_rob_node = max(left) + max(right)Don't rob current node, take max of rob or not rob children
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public int rob(TreeNode root) {
        int[] res = dfs(root);
        return Math.max(res[0], res[1]);
    }

    private int[] dfs(TreeNode node) {
        if (node == null) return new int[]{0, 0};
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        int rob = node.val + left[0] + right[0];
        int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[]{notRob, rob};
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(2);
        root.left.right = new TreeNode(3);
        root.right = new TreeNode(3);
        root.right.right = new TreeNode(1);
        Solution sol = new Solution();
        System.out.println(sol.rob(root)); // Output: 7
    }
}
Line Notes
private int[] dfs(TreeNode node)Returns array with two states: notRob and rob
if (node == null) return new int[]{0, 0};Base case returns zero for both states
int rob = node.val + left[0] + right[0];Rob current node plus not robbing children
int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);Don't rob current node, take max of rob or not rob children
#include <iostream>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    pair<int,int> dfs(TreeNode* node) {
        if (!node) return {0,0};
        auto left = dfs(node->left);
        auto right = dfs(node->right);
        int rob = node->val + left.first + right.first;
        int notRob = max(left.first, left.second) + max(right.first, right.second);
        return {notRob, rob};
    }

    int rob(TreeNode* root) {
        auto res = dfs(root);
        return max(res.first, res.second);
    }
};

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(2);
    root->left->right = new TreeNode(3);
    root->right = new TreeNode(3);
    root->right->right = new TreeNode(1);
    Solution sol;
    cout << sol.rob(root) << endl; // Output: 7
    return 0;
}
Line Notes
pair<int,int> dfs(TreeNode* node)Returns pair (notRob, rob) for node
if (!node) return {0,0};Base case returns zero for both states
int rob = node->val + left.first + right.first;Rob current node plus not robbing children
int notRob = max(left.first, left.second) + max(right.first, right.second);Don't rob current node, take max of rob or not rob children
function TreeNode(val, left=null, right=null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function rob(root) {
    function dfs(node) {
        if (!node) return [0, 0];
        const left = dfs(node.left);
        const right = dfs(node.right);
        const rob = node.val + left[0] + right[0];
        const notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return [notRob, rob];
    }
    const res = dfs(root);
    return Math.max(res[0], res[1]);
}

// Example usage:
// const root = new TreeNode(3, new TreeNode(2, null, new TreeNode(3)), new TreeNode(3, null, new TreeNode(1)));
// console.log(rob(root)); // Output: 7
Line Notes
function dfs(node)Returns array [notRob, rob] for node
if (!node) return [0, 0];Base case returns zero for both states
const rob = node.val + left[0] + right[0];Rob current node plus not robbing children
const notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);Don't rob current node, take max of rob or not rob children
⏱
Complexity
TimeO(n)
SpaceO(n) due to recursion stack

Each node is visited once in post-order traversal.

💡 For n=10^5, this approach is efficient and scalable.
Interview Verdict: Accepted

This is the optimal and cleanest approach for this problem.

📊
All Approaches - One-Glance Tradeoffs
💡 Bottom-up DP with post-order traversal is the best approach to implement in interviews due to clarity and efficiency.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(2^n)O(n) recursion stackYes (deep recursion)NoMention only - never code
2. Top-Down MemoizationO(n)O(n) recursion stack + memoYes (deep recursion)YesGood to mention and code if comfortable
3. Bottom-Up DP (Post-Order)O(n)O(n) recursion stackYes (deep recursion)YesBest approach to code in interview
💼
Interview Strategy
💡 Use this guide to understand the problem deeply, practice coding all approaches, and learn how to explain your thought process clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Explain the brute force recursive approach to show understanding.Step 3: Introduce memoization to optimize recursion.Step 4: Present bottom-up DP with post-order traversal as the optimal solution.Step 5: Code the bottom-up DP solution and test with examples.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Interviewer tests your understanding of tree DP, ability to optimize recursion with memoization, and clarity in explaining state definitions and transitions.

Common Follow-ups

  • What if the tree is a linked list? → The problem reduces to House Robber I.
  • Can you reconstruct which nodes were robbed? → Yes, by tracking choices during DP.
💡 These follow-ups test your ability to adapt solutions and extend them to practical scenarios.
🔍
Pattern Recognition

When to Use

1) Problem involves trees, 2) Need to optimize choices with constraints on adjacency, 3) Maximize sum or value, 4) Overlapping subproblems exist.

Signature Phrases

cannot rob two directly connected housesmaximum amount of moneybinary tree structure

NOT This Pattern When

Problems involving arbitrary graphs or no adjacency constraints are different and require other techniques.

Similar Problems

House Robber I - linear array version of the problemHouse Robber II - circular array versionBinary Tree Maximum Path Sum - similar tree DP but different constraints

Practice

(1/5)
1. Consider this modified Morris inorder traversal code snippet. Which line contains a subtle bug that can cause infinite loops or incorrect output on some trees?
def inorderTraversal(root):
    result = []
    current = root
    while current:
        if not current.left:
            result.append(current.val)
            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:
                # BUG: missing line to remove thread
                result.append(current.val)
                current = current.right
    return result
medium
A. Missing line resetting predecessor.right = None to remove thread
B. Line moving current to current.left after creating thread
C. Line appending current.val after detecting thread
D. Line setting predecessor.right = current (creating thread)

Solution

  1. Step 1: Identify thread removal step

    Morris traversal requires removing the temporary thread by setting predecessor.right = None after visiting the node.
  2. Step 2: Locate missing removal

    The code lacks the line resetting predecessor.right = None, causing infinite loops or corrupted tree structure.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Without removing thread, traversal loops endlessly [OK]
Hint: Always remove threads to restore tree [OK]
Common Mistakes:
  • Forgetting to remove thread
  • Appending node before removing thread
  • Incorrectly creating thread
2. The following code attempts to count nodes in a complete binary tree using the optimal approach. Identify the line containing the subtle bug that can cause incorrect counts for incomplete last levels.
def exists(idx, h, root):
    left, right = 0, 2**(h - 1) - 1
    for _ in range(h - 1):
        mid = (left + right) // 2
        if idx < mid:  # Bug here
            root = root.left
            right = mid
        else:
            root = root.right
            left = mid + 1
    return root is not null
medium
A. Line with 'if idx < mid:'
B. Line with 'return root is not null'
C. Line with 'root = root.right'
D. Line with 'left, right = 0, 2**(h - 1) - 1'

Solution

  1. Step 1: Understand binary search condition

    The condition should be 'if idx <= mid' to correctly include mid index in left subtree.
  2. Step 2: Identify impact of bug

    Using 'idx < mid' excludes mid index from left subtree, causing incorrect traversal and wrong node existence checks.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Correct binary search must include mid index [OK]
Hint: Binary search must use <= to include mid index [OK]
Common Mistakes:
  • Using < instead of <= in binary search condition
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. The following code attempts to count the number of paths summing to targetSum using iterative DFS and prefix sums. Which line contains a subtle bug that causes incorrect path counts?
class Solution:
    def pathSum(self, root, targetSum):
        if not root:
            return 0
        prefix_counts = {0: 1}
        result = 0
        stack = [(root, 0, False)]  # node, current_sum, visited_children

        while stack:
            node, current_sum, visited = stack.pop()
            if node is None:
                continue
            if not visited:
                current_sum += node.val
                result += prefix_counts.get(current_sum - targetSum, 0)
                prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1
                stack.append((node, current_sum, True))  # Mark node as visited
                stack.append((node.right, current_sum, False))
                stack.append((node.left, current_sum, False))
            else:
                # BUG: Missing decrement of prefix_counts on backtrack
                # prefix_counts[current_sum] -= 1
                pass

        return result
medium
A. Line where prefix_counts[current_sum] should be decremented but is missing
B. Line where prefix_counts[current_sum] is incremented
C. Line where current_sum is incremented by node.val
D. Line where stack appends left and right children

Solution

  1. Step 1: Identify prefix_counts usage

    prefix_counts tracks how many times a prefix sum has occurred along the current path.
  2. Step 2: Recognize missing decrement on backtrack

    Failing to decrement prefix_counts[current_sum] when backtracking causes counts to accumulate incorrectly across branches.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Missing decrement leads to overcounting paths [OK]
Hint: Always decrement prefix_counts on backtrack [OK]
Common Mistakes:
  • Not decrementing prefix_counts after visiting children
  • Assuming prefix_counts only grows
  • Confusing when to mark node as visited
5. Suppose you want to perform a preorder traversal on a binary tree where nodes can have parent pointers but no left or right pointers. Which approach correctly adapts preorder traversal to this scenario without extra space?
hard
A. Use a modified iterative approach that tracks previously visited nodes to avoid revisiting
B. Use recursion on parent pointers to simulate traversal
C. Iteratively traverse using parent pointers and a stack to track visited nodes
D. Use Morris traversal by creating temporary threaded links on parent pointers

Solution

  1. Step 1: Understand traversal constraints

    Without left/right pointers, standard Morris or recursion is not applicable; parent pointers only allow upward traversal.
  2. Step 2: Identify correct approach

    Tracking previously visited nodes iteratively allows preorder traversal by moving up/down without extra space for recursion stack.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Modified iterative approach handles parent-only trees without extra space [OK]
Hint: Parent-only trees require tracking visited nodes iteratively [OK]
Common Mistakes:
  • Trying to use recursion without child pointers
  • Attempting Morris traversal on parent pointers
  • Using stack without tracking visited nodes
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard