0

Path between two nodes of an implicit Fibonacci tree

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Path between two nodes of an implicit Fibonacci tree

Companies: Databricks

Difficulty: Hard

Problem statement

A Fibonacci tree of order k is a binary tree defined recursively:

  • Orders 0 and 1 are a single node.
  • For k >= 2, the root's left subtree is a Fibonacci tree of order k - 2 and its right subtree is a Fibonacci tree of order k - 1.

The nodes of a tree of order n are labeled 0, 1, 2, ... in preorder (root, then the left subtree, then the right subtree).

Implement:

def find_path(order: int, start: int, dest: int) -> str

Return the shortest sequence of moves from node start to node dest, where "U" moves to the parent, "L" to the left child and "R" to the right child. Return "" when start == dest, and raise an error if a label is not in the tree.

Constraints

  • 0 <= order <= 200. The tree has an exponential number of nodes, so you cannot build it.
  • start and dest are labels of the tree of that order.

Example 1. Order 3 has 5 nodes: 0 is the root, 1 is its left child (a leaf), 2 is its right child, and 3, 4 are the left and right children of 2.

  • find_path(3, 1, 4) returns "URR".
  • find_path(3, 0, 3) returns "RL".

Example 2. Order 4 has 9 nodes; the left subtree holds labels 1..3 and the right subtree holds 4..8.

  • find_path(4, 2, 8) returns "UURRR".

Follow-ups may ask for the list of node labels on the path, the distance only, or the same question with inorder labels.

Approach

This is LeetCode 2096 ("directions from one node to another") on a tree you are not allowed to build. A Fibonacci tree of order n has about phi^n nodes, so for n = 80 there are more nodes than atoms you can afford to allocate. The labels are preorder numbers, and preorder numbers plus subtree sizes tell you everything about where a node sits.

Brute force. Build the tree recursively, assign preorder labels, store parent pointers, find both nodes, and walk up from each to the root to find the lowest common ancestor (LCA). That is O(size of tree) time and memory, which is exponential in n. It is a good way to check your understanding of the shape on small n, and a good thing to say first, but it fails as soon as n grows past about 30.

Key fact: subtree sizes follow a Fibonacci-like recurrence.

size(0) = size(1) = 1
size(k) = 1 + size(k - 2) + size(k - 1)

In a preorder labeling of a subtree of order k whose root has label base:

  • the root is base;
  • the left subtree (order k - 2) holds labels base + 1 .. base + size(k - 2);
  • the right subtree (order k - 1) starts at base + 1 + size(k - 2).

So to find a label x, start at the root with base = 0 and order n. If x == base, stop. If x falls in the left range, record L, move to base + 1, order k - 2. Otherwise record R, move to base + 1 + size(k - 2), order k - 1. Each step lowers the order by at least 1, so the path from the root is at most n moves long.

Optimal method.

  1. Precompute size(0..n) once (O(n)).
  2. Compute the root-to-node move string for start and for dest.
  3. The LCA is the end of their longest common prefix of moves (same reasoning as 2096: two root paths agree exactly until they split).
  4. The answer is "U" once for every move left in the start path after the prefix, followed by the rest of the dest path.

If you are asked for the node labels on the path instead of moves, record the label at each step of the descent and stitch: start path reversed up to the LCA, then the dest path below it.

Invariants.

  • During the descent, base <= x < base + size(order); the target is always inside the current subtree.
  • order drops by 1 or 2 per step, so depth is at most n.
  • Labels are never stored for anything off the two root paths.

Edge cases to state up front.

  • start == dest returns the empty string.
  • One node is an ancestor of the other: the answer is all Us or has no Us.
  • Labels outside [0, size(n)) raise ValueError.
  • Orders 0 and 1 are a single node (label 0).
  • Sizes grow exponentially; Python integers are unbounded, but in Java or C++ say that size(n) overflows 64 bits near n = 90, so either cap n or use big integers.

Code

from typing import List


class FibonacciTree:
    """Implicit Fibonacci tree of a given order with preorder labels from 0.

    Order 0 and order 1 are single nodes. For k >= 2 the tree of order k has
    left subtree of order k - 2 and right subtree of order k - 1.
    """

    def __init__(self, order: int) -> None:
        if order < 0:
            raise ValueError("order must be >= 0")
        self.order = order
        self.size: List[int] = [1] * max(2, order + 1)
        for k in range(2, order + 1):
            self.size[k] = 1 + self.size[k - 2] + self.size[k - 1]

    def node_count(self) -> int:
        return self.size[self.order]

    def _descend(self, label: int) -> tuple[str, List[int]]:
        """Return (moves from root, labels visited from root) for `label`."""
        if not 0 <= label < self.node_count():
            raise ValueError(f"label {label} is not in the tree")
        moves: List[str] = []
        labels: List[int] = [0]
        base, k = 0, self.order
        while label != base:
            # Only orders >= 2 have children; the range check guarantees it.
            left_size = self.size[k - 2]
            if label <= base + left_size:
                moves.append("L")
                base, k = base + 1, k - 2
            else:
                moves.append("R")
                base, k = base + 1 + left_size, k - 1
            labels.append(base)
        return "".join(moves), labels

    def directions(self, start: int, dest: int) -> str:
        """Moves from start to dest: 'U' = to parent, 'L'/'R' = to child."""
        a, _ = self._descend(start)
        b, _ = self._descend(dest)
        p = 0
        while p < len(a) and p < len(b) and a[p] == b[p]:
            p += 1
        return "U" * (len(a) - p) + b[p:]

    def path_labels(self, start: int, dest: int) -> List[int]:
        """Node labels on the path from start to dest, both included."""
        a, la = self._descend(start)
        b, lb = self._descend(dest)
        p = 0
        while p < len(a) and p < len(b) and a[p] == b[p]:
            p += 1
        # la[p] == lb[p] is the LCA.
        return la[p:][::-1] + lb[p + 1:]

    def distance(self, start: int, dest: int) -> int:
        return len(self.directions(start, dest))


def find_path(order: int, start: int, dest: int) -> str:
    return FibonacciTree(order).directions(start, dest)


if __name__ == "__main__":
    # Order 3: 0 root; 1 = left leaf; 2 = right child with children 3 and 4.
    assert FibonacciTree(3).node_count() == 5
    assert find_path(3, 1, 4) == "URR"
    assert find_path(3, 3, 4) == "UR"
    assert find_path(3, 0, 3) == "RL"
    assert find_path(3, 4, 0) == "UU"
    assert find_path(3, 2, 2) == ""
    # Order 4: left subtree 1..3, right subtree 4..8.
    t4 = FibonacciTree(4)
    assert t4.node_count() == 9
    assert t4.directions(2, 8) == "UURRR"
    assert t4.path_labels(2, 8) == [2, 1, 0, 4, 6, 8]
    assert t4.path_labels(8, 8) == [8]
    assert t4.distance(5, 7) == 3
    assert find_path(0, 0, 0) == "" and find_path(1, 0, 0) == ""
    # Large order: never builds the tree.
    big = FibonacciTree(200)
    last = big.node_count() - 1
    assert big.directions(0, last) == "R" * 199
    assert big.directions(1, last) == "U" + "R" * 199
    try:
        find_path(3, 0, 5)
        raise AssertionError("expected ValueError")
    except ValueError:
        pass
    print("all tests passed")

Complexity

  • Precompute sizes: O(n) time, O(n) space (big integers aside; each size(k) has O(k) bits).
  • _descend: at most n steps, so O(n) time and O(n) space for the move list.
  • directions, path_labels, distance: two descents plus a prefix scan, O(n) time and O(n) space.
  • The brute force is O(phi^n) time and memory, which is the point of the question.

Test cases

  • Order 3 (labels: 0 root, 1 left leaf, 2 right child, 3 and 4 its children):
    • find_path(3, 1, 4) -> "URR"
    • find_path(3, 3, 4) -> "UR" (siblings)
    • find_path(3, 0, 3) -> "RL" (start is the ancestor; no U)
    • find_path(3, 4, 0) -> "UU" (dest is the ancestor; only U)
    • find_path(3, 2, 2) -> ""
  • Order 4 (left subtree 1..3, right subtree 4..8):
    • directions(2, 8) -> "UURRR"
    • path_labels(2, 8) -> [2, 1, 0, 4, 6, 8]
    • distance(5, 7) -> 3
  • Orders 0 and 1: find_path(0, 0, 0) -> "".
  • Order 200: root to the last label -> "R" * 199, computed instantly without building anything.
  • Label out of range, e.g. find_path(3, 0, 5) -> ValueError.

Follow-ups

  1. Return the node labels, not moves. Record base at each descent step and stitch the two root paths at the LCA (path_labels above). Same O(n).
  2. Return only the distance. len(a) + len(b) - 2 * p. You can skip building strings and compare the two descents in lockstep, stopping the shared walk at the first split, which keeps O(1) extra space beyond the size table.
  3. Inorder or postorder labels. Only the range arithmetic changes. Inorder: the left subtree is base .. base + size(k-2) - 1, the root is base + size(k-2), the right subtree follows. Postorder: left first, then right, then the root is the last label base + size(k) - 1. The LCA and stitching logic are unchanged.
  4. Many queries on the same order. Keep the size table and answer each query in O(n). If queries hit the same nodes repeatedly, cache root paths per label. For q queries the total is O(n + q * n).
  5. Generalize the shape (for example left = order k - 1, right = order k - 2, or a k-ary "Fibonacci" tree). Any recursive tree whose subtree sizes depend only on the order works the same way: precompute sizes per order and descend by comparing the label to child ranges.

Interviewer expectations

Mid-level (L4)

  • Draws a small tree, labels it in preorder, and sees that a subtree's labels are a contiguous range.
  • Derives the size recurrence and the root-to-node descent.
  • Reuses the 2096 idea: common prefix of root paths, then Us plus the rest of the dest path. Handles start == dest.

Senior (L5)

  • Explains up front why building the tree fails (exponential size) and why depth is O(n).
  • Gives clean O(n) code with input validation, ancestor cases, and orders 0 and 1 handled.
  • Answers the label-path and distance follow-ups without restructuring the code.

Staff (L6+)

  • Separates the shape (size table, child ranges) from the traversal order, so inorder or postorder is a small change to one function.
  • Raises integer overflow in fixed-width languages and how to bound it.
  • Talks about batched queries, caching, and how the same technique applies to any implicit recursive structure (segment-tree indexing, rope offsets).

Sign in to comment, vote or remix.