Find shortest path in a Fibonacci-ordered tree
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
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.)
Quick Answer: This question evaluates understanding of recursive binary tree structures, preorder indexing, Fibonacci-like size relations, and arithmetic-based navigation for computing paths in an implicitly defined tree.
You are given an implicit binary tree T(order). T(0) and T(1) each contain a single node. For k >= 2, T(k) consists of a root, a left subtree T(k-1), and a right subtree T(k-2). Nodes are labeled from 0 to size(order)-1 using preorder traversal: root, then the entire left subtree, then the entire right subtree. The sizes satisfy size(0) = 1, size(1) = 1, and size(k) = 1 + size(k-1) + size(k-2). Given order, start, and end, return the unique shortest path from start to end as a list of node labels, without explicitly constructing the tree.
Constraints
- 0 <= order
- size(0) = 1 and size(1) = 1
- For k >= 2, size(k) = 1 + size(k-1) + size(k-2)
- 0 <= start, end < size(order)
- Aim for O(order) time and O(order) extra space
Examples
Input: (2, 1, 2)
Expected Output: [1, 0, 2]
Explanation: In T(2), node 1 is the left child and node 2 is the right child of root 0.
Input: (0, 0, 0)
Expected Output: [0]
Explanation: T(0) has exactly one node, so the path starts and ends at 0.
Input: (3, 3, 2)
Expected Output: [3, 1, 2]
Explanation: In T(3), nodes 3 and 2 are both under node 1, so the shortest path goes through 1.
Input: (4, 4, 5)
Expected Output: [4, 2, 1, 5]
Explanation: Both nodes are in the left subtree of T(4); their lowest common ancestor is node 1.
Input: (5, 9, 14)
Expected Output: [9, 7, 1, 0, 10, 14]
Explanation: The nodes lie in different major branches of T(5), so the path passes through the overall root 0.
Input: (4, 0, 8)
Expected Output: [0, 6, 8]
Explanation: Node 8 is in the right subtree of the root in T(4), specifically under node 6.
Input: (4, 7, 7)
Expected Output: [7]
Explanation: When start and end are the same node, the shortest path contains only that label.
Hints
- Precompute size(k). In preorder, every subtree occupies one contiguous range of labels.
- Find the path from the root to start and to end using only range checks, then combine them through their lowest common ancestor.