Find Path Between Fibonacci Tree Nodes
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given a special family of binary trees called **Fibonacci trees**.
Define the tree `T(k)` recursively:
- `T(1)` is a single node.
- `T(2)` is a single node.
- For `k >= 3`, `T(k)` consists of a root node whose:
- left subtree is `T(k - 1)`
- right subtree is `T(k - 2)`
Let `size(k)` be the number of nodes in `T(k)`:
- `size(1) = 1`
- `size(2) = 1`
- `size(k) = 1 + size(k - 1) + size(k - 2)` for `k >= 3`
Now number all nodes of `T(k)` using **preorder traversal** (`root -> left -> right`) with **1-based indices** from `1` to `size(k)`.
Given:
- an integer `k` where `1 <= k <= 60`
- two preorder indices `a` and `b` such that `1 <= a, b <= size(k)`
Implement a function:
`List<Long> pathInFibonacciTree(long k, long a, long b)`
Return the sequence of preorder indices along the unique simple path from node `a` to node `b` in `T(k)`.
Requirements:
- The returned list must start with `a` and end with `b`.
- The tree may be extremely large, so you must **not** construct the full tree explicitly in memory.
- Your algorithm should determine the path using only the recursive structure of the Fibonacci tree.
Quick Answer: This question evaluates a candidate's ability to reason about recursive tree structures, map preorder indices to positions in a recursively defined Fibonacci tree, and design space-efficient algorithms for large inputs.
A Fibonacci tree T(k) is defined recursively: T(1) and T(2) each consist of a single node. 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), so size(1) = 1, size(2) = 1, and size(k) = 1 + size(k - 1) + size(k - 2). The nodes of T(k) are numbered in preorder (root, then left subtree, then right subtree) using 1-based indices from 1 to size(k). Given k and two valid preorder indices a and b, return the sequence of preorder indices along the unique simple path from node a to node b. The path must start with a and end with b. You must not construct the tree explicitly in memory.
Constraints
- 1 <= k <= 60
- 1 <= a, b <= size(k), where size(1) = 1, size(2) = 1, and size(i) = 1 + size(i - 1) + size(i - 2)
- Do not construct the full tree explicitly; solve using subtree sizes and preorder index ranges
Examples
Input: (1, 1, 1)
Expected Output: [1]
Explanation: T(1) has only one node, so the path from 1 to 1 is just [1].
Input: (3, 2, 3)