Finding a path between two nodes in a k-th order fibonacci tree

There is a binary fibonacci tree where the left subtree has order(n-2) and right subtree has order(n-1). When we construct the tree, we label the nodes in pre-order way with root starting with 0, so that each node has a unique value.

5th order fibonacci tree before and after re-labeling:

Let's say that we want to find the steps needed to get from one node to another. To get from 5 to 7, we output "UUURL" where U means up, L means left child, R means right child.

I think computing this output is pretty straightforward by constructing the second tree, then finding the lowest common ancestor of the two nodes. It is basically the same as the solutions for following problem: https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/

Is there another solution using dynamic programming? I feel like there should be a way to take advantage of the fibonacci properties instead of treating is a regular tree and doing a full traversal.

Edit: The input is the order of the fibonacci tree, source number, and destination number. For the given example, the input would be

order: 5
source: 5
dest: 7

The Python solution below decomposes the problem into three pieces.

1. Data types for a tree with a method that converts a depth-first index to a path (classes Leaf and Branch). This is a classic method to augment a tree for access by index.

2. Construction of the Fibonacci tree of the requested order, using the aforementioned data types. This is efficient due to sharing.

3. Conversion of two down paths to an up path followed by a down path.

I have optimized for clarity at the expense of efficiency, but the ideas here give an algorithm that runs in time O(order).

class Leaf:
    def __len__(self):
        return 1

    def path(self, dest):
        assert 0 <= dest < len(self)
        return ""


class Branch:
    def __init__(self, left, right):
        self._left = left
        self._right = right
        self._len = 1 + len(left) + len(right)

    def __len__(self):
        return self._len

    def path(self, dest):
        assert 0 <= dest < len(self)
        if dest < 1:
            return ""
        dest -= 1
        if dest < len(self._left):
            return "L" + self._left.path(dest)
        dest -= len(self._left)
        return "R" + self._right.path(dest)


def fib_tree(order):
    fib_trees = [Leaf(), Leaf()]
    while len(fib_trees) <= order:
        fib_trees.append(Branch(fib_trees[-2], fib_trees[-1]))
    return fib_trees[order]


def left_divide(source_path, dest_path):
    n = min(len(source_path), len(dest_path))
    i = min((j for j in range(n) if source_path[j] != dest_path[j]), default=n)
    return "U" * (len(source_path) - i) + dest_path[i:]


def fib_path(order, source, dest):
    tree = fib_tree(order)
    return left_divide(tree.path(source), tree.path(dest))


print(fib_path(5, 5, 7))
# UUURL