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.
A k-order Fibonacci tree F(k) is defined recursively:
- F(0) and F(1) each consist of a single node (the root).
- For k >= 2, F(k) has a root whose left subtree is F(k-2) and right subtree is F(k-1).
All nodes are assigned integer ids using a preorder traversal (root, then left subtree, then right subtree), starting from id 0 at the overall root.
Given k and two node ids a and b (both valid ids in F(k)), return the sequence of node ids along the unique simple path from a to b (inclusive), in order from a to b.
You must not explicitly build the tree.
Constraints
- 0 <= k <= 2000
- 0 <= a, b < size[k], where size[0]=size[1]=1 and size[k]=1+size[k-2]+size[k-1] for k>=2
- Do not build the explicit tree structure
Examples
Input: (2, 1, 2)
Expected Output: [1, 0, 2]
Explanation: F(2) has nodes [0(root), 1(left leaf), 2(right leaf)]. Path 1->2 goes through the root: 1-0-2.
Input: (4, 2, 8)
Expected Output: [2, 1, 0, 4, 6, 8]
Explanation: In F(4), node 2 is in the left subtree, node 8 in the right subtree; the path goes up to root 0 then down into the right side.
Input: (4, 5, 7)
Expected Output: [5, 4, 6, 7]
Explanation: Both nodes are inside the right subtree of root 0, with LCA at node 4.
Input: (5, 6, 14)
Expected Output: [6, 10, 12, 14]
Explanation: In F(5), node 6 is an ancestor of node 14, so the path is simply descending from 6 to 14.
Input: (5, 3, 14)
Expected Output: [3, 1, 0, 6, 10, 12, 14]
Explanation: LCA is the global root 0; path goes from 3 up to 0, then down to 14.