Path Between Two Preorder-Numbered Nodes of an Implicit Fibonacci Tree
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Fibonacci trees are defined recursively. `T(1)` and `T(2)` are single-node trees. For `k >= 3`, `T(k)` has a root whose left subtree is `T(k - 1)` and whose right subtree is `T(k - 2)`. Let `size(k)` be the number of nodes in `T(k)`: `size(1) = 1`, `size(2) = 1`, and `size(k) = 1 + size(k - 1) + size(k - 2)`.
Nodes are numbered 1, 2, 3, ... in the order a preorder traversal (root, then left subtree, then right subtree) visits them, so the root is node 1.
Given the order `k` and two nodes `a` and `b`, identified by their preorder numbers, return the preorder numbers of the nodes on the unique simple path from `a` to `b`. You must not construct the tree explicitly; for large `k` it has trillions of nodes.
### Function Signature
```python
def path_in_fibonacci_tree(k: int, a: int, b: int) -> list[int]:
```
### Rules
- The returned list starts with `a`, ends with `b`, and lists the nodes in the order the path visits them. The original interface accepted the nodes in any order; this console fixes the order so the answer is unique.
- If `a == b`, return `[a]`.
- Each node on the path appears exactly once.
### Constraints
- `1 <= k <= 60`
- `1 <= a, b <= size(k)`
- `size(60) = 3,096,017,511,839`, which exceeds `2^31 - 1` but stays below `2^53`; use 64-bit integers in fixed-width languages.
### Examples
For reference, here is `T(5)` numbered in preorder (the left child is listed first):
```text
1
+-- 2
| +-- 3
| | +-- 4
| | +-- 5
| +-- 6
+-- 7
+-- 8
+-- 9
```
**Example 1**
```text
k = 5, a = 4, b = 9
Output: [4, 3, 2, 1, 7, 9]
```
**Example 2**
```text
k = 5, a = 6, b = 5
Output: [6, 2, 3, 5]
```
**Example 3**
```text
k = 3, a = 2, b = 2
Output: [2]
```
Overview: Given the order of a recursively defined Fibonacci tree and two nodes labeled by preorder number, return the path between them without building a tree that can hold trillions of nodes. Tests recursive subtree-size reasoning, implicit tree navigation and 64-bit index arithmetic.
A Fibonacci tree of order k, written T(k), is defined recursively. T(1) and T(2) are single-node trees. For k >= 3, T(k) has a root whose left subtree is T(k - 1) and whose right subtree is T(k - 2). Let size(k) be the number of nodes in T(k): size(1) = 1, size(2) = 1, and size(k) = 1 + size(k - 1) + size(k - 2).
The nodes are numbered 1, 2, 3, ... in the order a preorder traversal (root, then left subtree, then right subtree) visits them, so the root is node 1.
Given the order k and two nodes a and b, identified by their preorder numbers, return the preorder numbers of the nodes on the unique simple path from a to b. You must not construct the tree explicitly; for large k it has trillions of nodes.
Output rules:
- The returned list starts with a, ends with b, and lists the nodes in the order the path visits them. a may be smaller or larger than b; the list always runs from a to b.
- If a == b, return [a].
- Each node on the path appears exactly once.
Node numbers can exceed 2^31 - 1: size(60) = 3,096,017,511,839. Every value stays below 2^53, so use 64-bit integers in fixed-width languages (long in Java, long long in C++); JavaScript numbers represent them exactly.
For reference, here is T(5) numbered in preorder (the left child is listed first):
1
+-- 2
| +-- 3
| | +-- 4
| | +-- 5
| +-- 6
+-- 7
+-- 8
+-- 9
Example 1:
Input: k = 5, a = 4, b = 9
Output: [4, 3, 2, 1, 7, 9]
Explanation: node 4 climbs through 3 and 2 to the root 1, then the path descends through 7 to 9.
Example 2:
Input: k = 5, a = 6, b = 5
Output: [6, 2, 3, 5]
Explanation: the path climbs from 6 to node 2, the deepest node above both endpoints, then descends through 3 to 5.
Constraints:
- 1 <= k <= 60
- 1 <= a, b <= size(k)
- size(60) = 3,096,017,511,839, which exceeds 2^31 - 1 but stays below 2^53; use 64-bit integers in fixed-width languages.
Constraints
- 1 <= k <= 60
- 1 <= a, b <= size(k), where size(1) = size(2) = 1 and size(k) = 1 + size(k - 1) + size(k - 2)
- size(60) = 3,096,017,511,839, which exceeds 2^31 - 1 but stays below 2^53; use 64-bit integers in fixed-width languages (long in Java, long long in C++)
Examples
Input: (1, 1, 1)
Expected Output: [1]
Explanation: Minimum valid: T(1) is a single node, so the path from node 1 to itself is [1].
Input: (2, 1, 1)
Expected Output: [1]
Explanation: Minimum valid: T(2) is also a single node.
Hints
- In preorder, a subtree's root comes first, followed by every node of its left subtree and then every node of its right subtree, so each subtree covers one contiguous block of numbers whose length is its size.
- T(k) has depth at most k - 2, so any path you report is short even when the node numbers reach the trillions.
- The path from a to b turns around at the deepest node that lies above both of them.