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.)