Katkat
Back

Find path between nodes in Fibonacci tree

DatabricksSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to navigate implicit tree structures defined by recurrence relations and your proficiency in pathfinding within large graphs without materializing them.

Fibonacci Tree Pathfinding

A Fibonacci tree T(n) is defined recursively:

  • T(0) is a single node (the root).
  • T(1) is a single node (the root).
  • T(n) for n > 1 has a root node with two children: T(n-1) as the left subtree and T(n-2) as the right subtree.

The nodes are indexed using a pre-order traversal starting from 1 at the root. For T(n), the root is index 1. If the root has children, the left subtree contains the next size(T(n-1)) nodes, followed by the right subtree containing the next size(T(n-2)) nodes.

Given an integer n (representing the height of the tree) and two node indices u and v, write a function that returns the shortest path between u and v in the tree. The path should be represented as a list of indices starting from u and ending at v.

Constraints

  • n can be up to 80.
  • u, v are valid indices within the tree.
  • Time complexity should be proportional to O(n).

Example

For n=3:

  • T(0) size = 1, T(1) size = 1, T(2) size = 2, T(3) size = 3.
  • The indices are: Root(1) -> Left Child(2) -> Left Child's Left(3).
  • path(3, 1, 3) -> [1, 2, 3]

Note

You may assume the tree is large enough that you need to use 64-bit integers. Pre-calculate the sizes of T(0) through T(n) before navigating.

Hints

Hint 1

First, pre-calculate the sizes of all Fibonacci trees up to n, as the number of nodes in T(n) grows exponentially.

Hint 2

To find the path between two nodes, find their lowest common ancestor (LCA) by comparing their positions relative to the left and right subtree boundaries.

Hint 3

Construct the path from u to the LCA by moving up the tree, and then from the LCA to v by moving down.

Follow-up questions

  • How would you modify your solution if the tree was an infinite Fibonacci tree where n is not bounded?
  • What is the space complexity of your approach, and can you optimize it if we only need the path length instead of the nodes themselves?
  • How do you handle integer overflow if n exceeds 92, given that Fibonacci numbers grow beyond the capacity of a 64-bit signed integer?