Find path between nodes in Fibonacci tree
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given a recursively defined **Fibonacci tree** `F(k)`:
- `F(0)` is a single node.
- `F(1)` is a single node.
- For `k >= 2`, `F(k)` consists of:
- a root node,
- a left subtree that is `F(k-2)`,
- a right subtree that is `F(k-1)`.
All nodes are labeled with integer IDs using **preorder traversal** (visit root, then left subtree, then right subtree), starting from the root of `F(k)` having ID `0`.
Given:
- an integer `k`,
- two node IDs `a` and `b` (guaranteed to be valid IDs within `F(k)`),
return the **sequence of node IDs** along the unique simple path from node `a` to node `b` (inclusive).
### Requirements / Constraints
- You should **not build the explicit tree**.
- Assume `k` can be large enough that the total number of nodes grows quickly; use 64-bit arithmetic where possible and describe how you would handle potential overflow if needed.
### Example (format only)
If the path is `a -> ... -> b`, output something like:
`[a, ..., b]`
(Exact examples are not required; focus on the algorithm and correct path output.)
Quick Answer: This question evaluates understanding of recursive tree structures, preorder indexing, implicit tree representations, algorithmic reasoning about node-to-node paths, and awareness of combinatorial size growth and integer overflow.