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.