Recursion, Dynamic Programming, And Implicit Structures

What's being tested

These problems probe mastery of recursion on an implicit tree: compute and use subtree sizes given a Fibonacci-like recurrence, then map preorder indexes to tree paths with index arithmetic. Interviewers check correctness, off-by-one handling, and efficient traversal without materializing the whole tree.

Patterns & templates

• Compute subtree sizes with the Fibonacci recurrence and memoize (`getSize(k)`); this is O(k) to build, constant-time lookups thereafter.
• Preorder index navigation: compare target index to `left_size` + 1 to decide left/root/right; iterate until leaf — O(height) steps.
• Iterative recursion: replace recursive descent with a loop that updates node rank and subtree order to avoid stack depth issues.
• Path encoding: emit directions (`L`/`R`) while descending; reconstruct node-to-node path by computing LCA via index-to-path conversion.
• Dynamic programming on indices: cache computed path segments or sizes across queries to answer multiple path requests in O(height) each.
• Guard against overflow: cap Fibonacci sizes at `INT64_MAX` and clamp indices; check for invalid indexes early.

Common pitfalls

Pitfall: Off-by-one errors when treating `left_size`, root position, and right subtree start — always test small k (1..4) to validate indexing.

Pitfall: Assuming tree height is log(n); for Fibonacci trees height ≈ index k, so complexity must be in terms of k, not total nodes.

Pitfall: Using recursion without tail-call elimination can blow the stack for deep k — prefer iterative descent or explicit stack.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.