Path between two nodes of an implicit Fibonacci tree

A Fibonacci tree of order k is a binary tree defined recursively:

• Orders 0 and 1 are a single node.
• For k >= 2, the root's left subtree is a Fibonacci tree of order k - 2 and its right subtree is a Fibonacci tree of order k - 1.

The nodes of a tree of order n are labeled 0, 1, 2, ... in preorder (root, then the left subtree, then the right subtree).

Implement:

def find_path(order: int, start: int, dest: int) -> str

Return the shortest sequence of moves from node start to node dest, where "U" moves to the parent, "L" to the left child and "R" to the right child. Return "" when start == dest, and raise an error if a label is not in the tree.

Constraints

• 0 <= order <= 200. The tree has an exponential number of nodes, so you cannot build it.
• start and dest are labels of the tree of that order.

Example 1. Order 3 has 5 nodes: 0 is the root, 1 is its left child (a leaf), 2 is its right child, and 3, 4 are the left and right children of 2.

• find_path(3, 1, 4) returns "URR".
• find_path(3, 0, 3) returns "RL".

Example 2. Order 4 has 9 nodes; the left subtree holds labels 1..3 and the right subtree holds 4..8.

• find_path(4, 2, 8) returns "UURRR".

Follow-ups may ask for the list of node labels on the path, the distance only, or the same question with inorder labels.