Find path in implicit Fibonacci tree

You are given a special family of binary trees called Fibonacci trees. The k‑th order Fibonacci tree T(k) is defined recursively:

• T(1) is a single node.
• T(2) is a single node.
• For k ≥ 3, T(k) is a tree whose root has:
  • left subtree T(k − 1) and
  • right subtree T(k − 2).

Let size(k) be the number of nodes in T(k). You can compute size(k) from the definition above:

• size(1) = 1
• size(2) = 1
• size(k) = 1 + size(k − 1) + size(k − 2) for k ≥ 3

Now, imagine we number the nodes of T(k) in preorder (root, then left subtree, then right subtree), using 1‑based indices from 1 to size(k).

You are given:

• An integer k (the order of the Fibonacci tree), with 1 ≤ k ≤ 60.
• Two integers a and b, such that 1 ≤ a, b ≤ size(k); these are indices of two nodes in the preorder numbering of T(k).

The tree can be very large for big k, so you must not construct it explicitly in memory.

Task

Design and implement a function:

List<Long> pathInFibonacciTree(long k, long a, long b)

that returns the sequence of node indices (in preorder numbering) along the simple path from node a to node b in T(k).

• The path should start with a and end with b.
• Indices in the returned list should be the preorder indices in T(k).

Constraints and requirements:

• k can be as large as 60 (or similar), so size(k) may be large (up to around 10^12). Use 64‑bit integers for sizes and indices.
• You must treat the tree implicitly:
  • Use the recursive structure and the sizes of subtrees to navigate.
  • You may not allocate O(size(k)) memory or explicitly build all nodes.
• Aim for an algorithm with time complexity polylogarithmic or at worst O(h), where h is the height of the tree (proportional to k), i.e., O(k) or similar.

Hints / clarifications

• Because of the preorder layout, for T(k):
  • The root always has index 1 in its own tree.
  • The left subtree T(k − 1) occupies indices [2, 1 + size(k − 1)] in T(k).
  • The right subtree T(k − 2) occupies the following range after that.
• You may find it helpful to implement helper functions that, given (k, indexRange, nodeIndex), determine whether the node lies in the left subtree, right subtree, or is the root.

Design your algorithm and helper functions so that you can:

1. Compute the path from each node up to the root (in terms of indices) without building the tree.
2. Combine these paths to construct the path from a to b via their lowest common ancestor (LCA).

Return the final path as a list of preorder indices.

Find Path in Implicit Fibonacci Tree

Find the path between two nodes of a Fibonacci tree using only its recursive structure — the tree may be far too large to build.

The Fibonacci tree

A Fibonacci tree T(k) is defined recursively:

• T(1) and T(2) each consist of a single node.
• For k >= 3, the root of T(k) has left subtree T(k - 1) and right subtree T(k - 2).

Its size (number of nodes) follows the matching recurrence:

• size(1) = 1, size(2) = 1
• size(k) = 1 + size(k - 1) + size(k - 2) for k >= 3

The nodes of T(k) are numbered in preorder (root, then the entire left subtree, then the entire right subtree), starting from 1. So the root is always node 1, the left subtree occupies a contiguous block of indices immediately after it, and the right subtree occupies the block after that.

Task

Implement:

def solution(k, a, b):

Given the tree order k and two preorder indices a and b, return the list of preorder indices visited along the unique simple path from node a to node b, in order.

Output format

• The returned list starts with a and ends with b, listing every node on the path between them (including both endpoints).
• The path runs a → ... → LCA → ... → b, where LCA is the lowest common ancestor of a and b. The LCA appears exactly once.
• If a == b, the path is the single node, so return [a].

Constraints

• 1 <= k <= 60
• 1 <= a, b <= size(k)
• Do not build the full tree explicitly — use its recursive structure and subtree sizes to navigate, since size(k) grows exponentially.

Examples

• solution(1, 1, 1) → [1]
• solution(4, 3, 5) → [3, 2, 1, 5]
• solution(5, 1, 9) → [1, 7, 9]
• solution(6, 7, 14) → [7, 3, 2, 1, 11, 12, 14]
• solution(6, 14, 7) → [14, 12, 11, 1, 2, 3, 7]

Hints

1. For a subtree T(t) rooted at global index r, the left subtree root is at r + 1 and occupies indices [r + 1, r + size(t - 1)]. The right subtree starts immediately after that block.
2. Compute the path from each target node up to the root using only index ranges. Then find the lowest common ancestor by comparing the two rootward paths from the end.

Approach

The trick is that a preorder numbering of a Fibonacci tree turns "which subtree contains node X" into pure arithmetic, so we never build the tree.

Subtree sizes. sizes[i] counts the nodes of T(i) via the Fibonacci-tree recurrence size(k) = 1 + size(k-1) + size(k-2) (with size(1)=size(2)=1). This is precomputed once.

Root-ward path (path_to_root). In preorder, a node's left subtree occupies the contiguous range [root+1, root+left_size] immediately after the root, and the right subtree follows it. Starting at the root (index 1, order k), we repeatedly test the target:

• if it lands in the left range, descend left: new root root+1, order k-1;
• otherwise descend right: new root root + 1 + left_size, order k-2.

Each visited root is pushed onto ancestors; the function returns [target] + reversed(ancestors) — i.e. the path from target up to the global root.

Stitching a→b. Both root-ward paths end at root 1, so their shared suffix is the path above the LCA. Comparing from the tail (i, j) inward, we walk past every common ancestor until the entries differ — the last matching node is the LCA. The answer is path_a up to and including the LCA, followed by path_b's portion below the LCA reversed: path_a[:i+2] + path_b[:j+1][::-1]. The +2/+1 indexing keeps the single LCA copy and drops the duplicate, giving the unique simple path a → LCA → b.

• Time complexity: O(k)
• Space complexity: O(k)