Shortest Path in a Fibonacci Tree

Problem: Shortest Path in a Fibonacci Tree Define a Fibonacci Tree T(n) as follows: T(0) and T(1) are both single-node trees. For n >= 2, the root of T(n) has two subtrees: the left subtree is T(n - 2); the right subtree is T(n - 1). Nodes are labeled from 1 to size(n) by an inorder traversal, where size(n) is the total number of nodes in T(n). Therefore, in T(n): the left subtree contains size(n - 2) nodes; the root label is size(n - 2) + 1; labels in the right subtree are shifted by size(n - 2) + 1. Given n and two node labels start and dest in T(n), return the shortest path from start to dest. The path consists of: 'U': move from the current node to its parent; 'L': move from the current node to its left child; 'R': move from the current node to its right child. If start == dest, return an empty string. Input Format n start dest Output Format path Print a string containing only U, L, and R. Constraints 0 <= n <= 10000 1 <= start, dest <= size(n) You should not explicitly build the whole tree because its size grows exponentially with n. Example 1 Input: 2 1 3 Output: UR Example 2 Input: 3 1 5 Output: URR Example 3 Input: 4 3 5 Output: UURL Example Input 2 1 3 Output UR