Path Between Two Preorder-Numbered Nodes of an Implicit Fibonacci Tree

Fibonacci trees are defined recursively. T(1) and T(2) are single-node trees. For k >= 3, T(k) has a root whose left subtree is T(k - 1) and whose right subtree is T(k - 2). Let size(k) be the number of nodes in T(k): size(1) = 1, size(2) = 1, and size(k) = 1 + size(k - 1) + size(k - 2).

Nodes are numbered 1, 2, 3, ... in the order a preorder traversal (root, then left subtree, then right subtree) visits them, so the root is node 1.

Given the order k and two nodes a and b, identified by their preorder numbers, return the preorder numbers of the nodes on the unique simple path from a to b. You must not construct the tree explicitly; for large k it has trillions of nodes.

Function Signature

def path_in_fibonacci_tree(k: int, a: int, b: int) -> list[int]:

Rules

• The returned list starts with a, ends with b, and lists the nodes in the order the path visits them. The original interface accepted the nodes in any order; this console fixes the order so the answer is unique.
• If a == b, return [a].
• Each node on the path appears exactly once.

Constraints

• 1 <= k <= 60
• 1 <= a, b <= size(k)
• size(60) = 3,096,017,511,839, which exceeds 2^31 - 1 but stays below 2^53; use 64-bit integers in fixed-width languages.

Examples

For reference, here is T(5) numbered in preorder (the left child is listed first):

1
+-- 2
| +-- 3
| | +-- 4
| | +-- 5
| +-- 6
+-- 7
 +-- 8
 +-- 9

Example 1

k = 5, a = 4, b = 9
Output: [4, 3, 2, 1, 7, 9]

Example 2

k = 5, a = 6, b = 5
Output: [6, 2, 3, 5]

Example 3

k = 3, a = 2, b = 2
Output: [2]