Katkat
Back

Find Path Between Fibonacci Tree Nodes

DatabricksSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to map nodes in a recursively defined tree structure without materializing the tree, requiring an understanding of Fibonacci sequences and path-finding algorithms in binary trees.

Problem Statement

Define a "Fibonacci Tree" T(n) recursively as follows:

  • T(0) is a single node.
  • T(1) is a single node.
  • T(n) for n > 1 is a tree with a root node, a left subtree T(n-1), and a right subtree T(n-2).

Each node in T(n) is assigned an index based on a preorder traversal (Root, Left, Right), starting from index 1. Given an integer n (the order of the tree) and two target node indices u and v, find the path from u to v in terms of directions ('L' for moving to a left child, 'R' for moving to a right child, 'P' for moving to a parent).

Constraints

  • n is up to 80 (where T(80) fits within a 64-bit integer range).
  • `1 1 ('P'), 1 -> 3 ('R'). Output: "PR".

Example 2:

  • n = 4. T(4) has structure: Root(1), Left(T3), Right(T2).
  • Path from 2 to 7: Output: "PRR".

Implementation

def get_fibonacci_path(n, u, v):
    # Return a string representing the shortest path from u to v
    pass

Note: Since the tree can be massive, you must not construct the tree in memory. Use the property that the number of nodes in T(n) is Fib(n+1) - 1 (or similar recurrence) to navigate the tree.

Hints

Hint 1

Precompute the number of nodes in each Fibonacci tree T(i) using the relation Nodes(i) = 1 + Nodes(i-1) + Nodes(i-2).

Hint 2

To find the path, define a function `get_path_to_root(n, target)` that returns the sequence of nodes and directions from the root (1) to the target.

Hint 3

The shortest path between u and v can be found by identifying the Lowest Common Ancestor (LCA) using the paths from the root to u and v.

Follow-up questions

  • How would you optimize the memory complexity to O(n) instead of storing the full path lists?
  • What changes if the traversal order was changed to Inorder or Postorder?
  • How does the time complexity change if we need to handle m path queries for a tree of order n?