Fibonacci Tree Path

A Fibonacci tree of order n is defined recursively:

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

Nodes are numbered 0, 1, 2, ... in preorder (a node, then its whole left subtree, then its whole right subtree). For example, the order-4 tree is numbered like this:

0
         /     \
        1       4
       / \     / \
      2   3   5   6
                 / \
                7   8

Given n and two node numbers start and dest, return the shortest path from start to dest as a string: first one "U" for each step up to a parent, then "L"/"R" for each step down to a left/right child. Return "" if start == dest.

The tree can have trillions of nodes, so it cannot be built explicitly.