Find shortest path in a Fibonacci-ordered tree

You are given a recursively-defined binary tree T(order) whose shape depends only on order (not on node values). Nodes are labeled 0..N-1 using preorder traversal (root, then left subtree, then right subtree), where N = size(T(order)).

Tree definition

Let size(k) be the number of nodes in T(k).

• Base cases: T(0) and T(1) each consist of a single node.
• Therefore: size(0) = 1, size(1) = 1.
• Recursive case: for k >= 2, T(k) has:
• a root node,
• a left subtree T(k-1),
• a right subtree T(k-2).

This implies:

• size(k) = 1 + size(k-1) + size(k-2)

Task

Given integers:

• order — which tree T(order) to use
• start — a node label in T(order)
• end — a node label in T(order)

Return the shortest path from start to end as a sequence of node labels, inclusive (i.e., the unique simple path in the tree).

You are not given a node/edge structure and should solve the problem using only arithmetic on integers plus order.

Input / Output

• Input: order: int, start: int, end: int
• Output: path: int[] (labels from start to end, inclusive)

Constraints

• 0 <= order
• 0 <= start, end < size(order)
• Aim for an algorithm that runs in O(order) time and uses O(order) extra space.

Example

For order = 2:

• size(0)=1, size(1)=1, size(2)=3
• Preorder labels are: root 0, left child 1, right child 2

If start=1, end=2, the output path is:

• [1, 0, 2]

(Any equivalent representation of the same path is acceptable if the problem statement in an interview clarifies formatting.)