This problem is a variation of LeetCode 2096: Step-By-Step Directions From a Binary Tree Node to Another. Solving that problem first is recommended if you have not done so.
A Fibonacci tree is constructed recursively as a binary tree. In a tree of order $$n$$, written as $$Fn(n)$$, the left subtree has order $$n - 2$$, while the right subtree has order $$n - 1$$. An order-3 Fibonacci tree is illustrated below.
For a Fibonacci tree with a given order, assign labels to its nodes in pre-order traversal, beginning at 0 and continuing through n - 1, where n denotes the tree's total number of nodes. Given the labels source and dest, produce the route from source to dest as a string of directional characters:
Constraints:
2 ≤ order≤ 100 ≤ source, dest ≤ n - 1Example 1:
order = 5, source = 5, dest = 7
"UUURL"
<img src="https://res.cloudinary.com/algro/image/upload/v1750280191/production/post/685303ac1af0034b3227652d/cpgouqtsdlwhlvr9tghs.jpg" alt="" height="400" width="900" /> The order-5 Fibonacci tree and its pre-order labels appear above. To travel from node 5 to node 7, take these moves: 5 → parent 3 ("U") 3 → parent 1 ("U") 1 → parent 0 ("U") 0 → right child 6 ("R") 6 → left child 7 ("L")
Example 2:
order = 4, source = 8, dest = 3
"UUULR"
Example 3:
order = 5, source = 4, dest = 13
"UUURRRL"
Example 1
Input: 5 5 7
Output: UUURL
Example 2
Input: 4 8 3
Output: UUULR