Find path in implicit Fibonacci tree
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
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:
```text
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.
Quick Answer: This question evaluates understanding of recursion, tree traversal, implicit data structures, and index arithmetic for navigating preorder-numbered Fibonacci trees and computing node-to-node paths.
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:
```python
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]`
Constraints
- 1 <= k <= 60
- 1 <= a, b <= size(k)
- Do not build the full tree explicitly; use its recursive structure and subtree sizes
Examples
Input: (1, 1, 1)
Expected Output: [1]
Input: (4, 3, 5)
Expected Output: [3, 2, 1, 5]
Input: (5, 4, 5)
Expected Output: [4, 3, 5]
Input: (5, 1, 9)
Expected Output: [1, 7, 9]
Input: (6, 7, 14)
Expected Output: [7, 3, 2, 1, 11, 12, 14]
Input: (6, 10, 10)
Expected Output: [10]
Input: (8, 1, 41)
Expected Output: [1, 27, 37, 41]
Solution
def solution(k, a, b):
max_k = max(2, k)
sizes = [0] * (max_k + 1)
sizes[1] = 1
sizes[2] = 1
for i in range(3, k + 1):
sizes[i] = 1 + sizes[i - 1] + sizes[i - 2]
def path_to_root(order, target):
root = 1
ancestors = []
while target != root:
ancestors.append(root)
left_size = sizes[order - 1]
left_root = root + 1
left_end = root + left_size
if left_root <= target <= left_end:
root = left_root
order -= 1
else:
root = root + 1 + left_size
order -= 2
return [target] + ancestors[::-1]
path_a = path_to_root(k, a)
path_b = path_to_root(k, b)
i = len(path_a) - 1
j = len(path_b) - 1
while i >= 0 and j >= 0 and path_a[i] == path_b[j]:
i -= 1
j -= 1
return path_a[:i + 2] + path_b[:j + 1][::-1]
Explanation
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).
Hints
- 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.
- 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.