Path Between Two Nodes in a Preorder-Numbered Fibonacci Tree
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
A Fibonacci tree is a binary tree defined by its order:
- The trees of order 0 and order 1 are each a single node.
- For `n >= 2`, the tree of order `n` is a root node whose left subtree is a Fibonacci tree of order `n - 1` and whose right subtree is a Fibonacci tree of order `n - 2`.
The nodes are numbered in preorder starting from 0: the root gets 0, then the nodes of the left subtree are numbered, then those of the right subtree, each subtree numbered the same way recursively.
Given the order of the tree and two node numbers, return the path from `source` to `target` as a string of moves, such as `"UUULLR"`: `'U'` moves to the parent, `'L'` moves to the left child and `'R'` moves to the right child.
The report gives the tree and the format of the path; the base cases and the preorder numbering are fixed here so that node numbers are unambiguous.
### Function Signature
```python
def fibonacci_tree_path(order: int, source: int, target: int) -> str:
```
### Rules
- In a tree, the path from `source` to `target` that never visits a node twice is unique; return that path. It consists of zero or more `'U'` moves followed by zero or more `'L'` and `'R'` moves.
- Return `""` when `source == target`.
### Constraints
- `0 <= order <= 70`
- The tree of order `n` has `size(n)` nodes, where `size(0) = size(1) = 1` and `size(n) = 1 + size(n - 1) + size(n - 2)` for `n >= 2`.
- `0 <= source < size(order)` and `0 <= target < size(order)`.
- `size(70) = 616,123,042,340,257`, so node numbers can exceed `2^31 - 1` and need 64-bit integers; every value stays below `2^53`.
- The returned path has at most `2 * order` characters.
### Examples
```text
Fibonacci tree of order 4, nodes numbered in preorder:
0
/ \
1 6
/ \ / \
2 5 7 8
/ \
3 4
```
**Example 1**
```text
Input: order = 4, source = 4, target = 7
Output: "UUURL"
```
From node 4, move up to 2, then 1, then 0; then move right to 6 and left to 7.
**Example 2**
```text
Input: order = 4, source = 1, target = 4
Output: "LR"
```
Node 1 is an ancestor of node 4: move left to 2, then right to 4.
**Example 3**
```text
Input: order = 5, source = 12, target = 6
Output: "UUULLR"
```
In the order-5 tree the root's left subtree (order 4) holds nodes 1 to 9 and its right subtree (order 3) holds nodes 10 to 14. Node 12 is the left child of 11, which is the left child of 10, the root's right child. Node 6 is the right child of 2, which is the left child of 1, the root's left child.
Overview: A tree coding problem on Fibonacci trees, where the tree of order n has a left subtree of order n-1 and a right subtree of order n-2, with nodes numbered in preorder. Given two node numbers, return the path between them as up, left and right moves, for trees whose node numbers go far beyond the 32-bit range.
Read the full Databricks Software Engineer interview experience this question came from
A Fibonacci tree is a binary tree defined by its order:
- The trees of order 0 and order 1 are each a single node.
- For `n >= 2`, the tree of order `n` is a root node whose left subtree is a Fibonacci tree of order `n - 1` and whose right subtree is a Fibonacci tree of order `n - 2`.
The nodes are numbered in preorder starting from 0: the root gets 0, then the nodes of the left subtree are numbered, then those of the right subtree, each subtree numbered the same way recursively.
Given the order of the tree and two node numbers `source` and `target`, return the path from `source` to `target` as a string of moves: `'U'` moves to the parent, `'L'` moves to the left child and `'R'` moves to the right child.
In a tree, the path from `source` to `target` that never visits a node twice is unique; return that path. It consists of zero or more `'U'` moves followed by zero or more `'L'` and `'R'` moves. Return `""` when `source == target`.
Node numbers can exceed `2^31 - 1` (the tree of order 70 has 616,123,042,340,257 nodes), so `source` and `target` are 64-bit integers (`long` in Java, `long long` in C++); every value stays below `2^53`.
**Example 1**
```text
Fibonacci tree of order 4, nodes numbered in preorder:
0
/ \
1 6
/ \ / \
2 5 7 8
/ \
3 4
Input: order = 4, source = 4, target = 7
Output: "UUURL"
```
From node 4, move up to 2, then 1, then 0; then move right to 6 and left to 7.
**Example 2**
```text
Input: order = 4, source = 1, target = 4
Output: "LR"
```
Node 1 is an ancestor of node 4: move left to 2, then right to 4.
**Constraints**
- `0 <= order <= 70`
- The tree of order `n` has `size(n)` nodes, where `size(0) = size(1) = 1` and `size(n) = 1 + size(n - 1) + size(n - 2)` for `n >= 2`.
- `0 <= source < size(order)` and `0 <= target < size(order)`.
- `size(70) = 616,123,042,340,257`, so node numbers can exceed `2^31 - 1` and need 64-bit integers; every value stays below `2^53`.
- The returned path has at most `2 * order` characters.
Constraints
- 0 <= order <= 70
- The tree of order n has size(n) nodes, where size(0) = size(1) = 1 and size(n) = 1 + size(n - 1) + size(n - 2) for n >= 2.
- 0 <= source < size(order) and 0 <= target < size(order).
- size(70) = 616,123,042,340,257, so node numbers can exceed 2^31 - 1 and need 64-bit integers (long in Java, long long in C++); every value stays below 2^53.
- The returned path has at most 2 * order characters.
Examples
Input: (0, 0, 0)
Expected Output: ''
Explanation: Order 0 is a single node; source == target == 0 gives the empty path.
Input: (1, 0, 0)
Expected Output: ''
Explanation: Order 1 is also a single node (no children); the empty path.
Hints
- The size recurrence tells you which range of preorder numbers belongs to a root's left subtree and which to its right subtree.
- The required path is some 'U' moves up to the lowest node shared by the routes from the root to source and to target, then 'L'/'R' moves down from it.
- At order 70 the tree has over 6 * 10^14 nodes, so it cannot be stored; work with node numbers and subtree sizes only.