Databricks Code: Shortest Path in a Fibonacci Tree

Problem summary

You are given order k and two node labels (start and end) in a preorder-labeled Fibonacci tree. T(0) and T(1) are single nodes; for k>=2, T(k) has left = T(k-2) and right = T(k-1). Labels are assigned by preorder and may be 0-based or 1-based. Your goal is to return the sequence of labels along the unique path between start and end (inclusive), without constructing the whole tree.

What you'll be asked to do (flow)

First, derive subtree sizes up to order k using the Fibonacci-like recurrence (you can compute these iteratively in O(k) time). Then, for each endpoint (start and end) descend from the root using label arithmetic: at each subtree decide whether the target label is the root, in the left range, or in the right range and update the current base label and order accordingly. Record the root-to-node label sequences for both endpoints. Find their longest common prefix to identify the lowest common ancestor (LCA), then stitch the final path by reversing the start->root segment up to the LCA and appending the LCA->end segment.

Skill signals interviewed

You should demonstrate: working with implicit/implicit-indexed trees, recursion/iterative descent, deriving and using subtree sizes (Fibonacci recurrence), handling 0/1-based label conventions, computing lowest common ancestor from root-to-node paths, and producing an algorithm that avoids allocating nodes proportional to the tree size. Explain correctness and give an analysis of time/space using k (tree order) and L (length of the returned path).