Apple Coding Question: Count Occurrences in Binary Tree

Problem overview

You are asked to count how many nodes in a binary tree contain a given target value. The baseline task is a correct, single-threaded implementation that traverses the tree and returns the exact count. Subsequent stages extend that core: one requires a parallel implementation that divides traversal among workers and safely aggregates partial counts, and another asks you to build an index or cache to answer repeated queries quickly.

What you'll be asked to do (flow / stages)

1. Implement count_occurrences(root, target) using a deterministic traversal (DFS or BFS) that returns the exact integer count.
2. Extend your solution to count_occurrences_parallel(root, target, num_workers) — partition work across multiple workers and combine results with thread-safe aggregation (e.g., per-worker counters + atomic sum or a mutex-protected accumulator). Document thread-safety properties and shared state usage.
3. Design build_index(root) and query_index(index, target) to precompute an auxiliary map from value -> frequency so repeated queries run in O(1) time. Optionally describe update operations and their consistency guarantees.

Skills and signals interviewers look for

• Correct traversal of binary trees (recursive or iterative DFS/BFS).
• Careful handling of concurrency: partitioning strategy, synchronization (locks, atomics, or concurrent accumulators), and avoiding lost updates.
• Time/space trade-offs for precomputation (hash map of frequencies), and how updates affect index consistency.
• Clear function signatures and complexity analysis (O(n) build, O(1) query, O(n/num_workers) per worker ideally).

You should be prepared to discuss partitioning strategies (subtree work queues, task splitting), synchronization choices, memory vs latency trade-offs, and how your index handles dynamic changes.