How should I practice Path Between Two Nodes of a Fibonacci Tree?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Databricks onsite interview problems in FastPrep.

Is Path Between Two Nodes of a Fibonacci Tree associated with Databricks?

FastPrep tags this as a Databricks onsite interview coding practice problem when the problem catalog has that company and stage context.

Path Between Two Nodes of a Fibonacci Tree

Databricks● MediumFULLTIMEONSITE INTERVIEW

Problem statement

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

For n = 0 or n = 1, the tree is a single node.
For n >= 2, the tree has a root whose left subtree is a Fibonacci tree of order n - 2 and whose right subtree is a Fibonacci tree of order n - 1.

The nodes are numbered in preorder starting from 0: the root receives the next number first, then every node in its left subtree, then every node in its right subtree. So the root is always node 0.

Given the tree order order and two node numbers fromNode and toNode, return the moves along the shortest path from fromNode to toNode. Write U for a move from a node to its parent, L for a move to its left child, and R for a move to its right child.

In a tree the shortest path is unique: it climbs from fromNode to the lowest common ancestor of the two nodes, then descends to toNode. Return all of its U moves followed by the downward moves in order. If fromNode equals toNode, return an empty string.

The tree can be far too large to build. Find the path from the subtree sizes instead.

Function

fibonacciTreePath(order: int, fromNode: int, toNode: int) → String

Examples

Example 1

order = 6fromNode = 12toNode = 4return = "UUULLR"

The order-6 tree has 25 nodes. Its left subtree has order 4 and holds nodes 1 through 9; its right subtree has order 5 and holds nodes 10 through 24.

From the root, node 12 is reached by R (node 10), L (node 11), L (node 12).
From the root, node 4 is reached by L (node 1), L (node 2), R (node 4).

The two routes share no first move, so the lowest common ancestor is the root. Climb three levels with UUU, then descend with LLR.

Example 2

order = 4fromNode = 3toNode = 8return = "UURRR"

The order-4 tree has 9 nodes. Node 0 is the root, nodes 1 through 3 form its left subtree of order 2, and nodes 4 through 8 form its right subtree of order 3.

Node 3 is the right child of node 1, so its route from the root is LR. Node 8 is reached by RRR through nodes 4 and 6. The lowest common ancestor is the root, so the answer is UU followed by RRR.

Example 3

order = 5fromNode = 10toNode = 13return = "RL"

In the order-5 tree, the right subtree of order 4 starts at node 6. Inside it, nodes 7 through 9 form the left subtree of order 2, and node 10 roots the right subtree of order 3. That subtree has left child 11 and right child 12, and node 12 has children 13 and 14.

Node 10 is an ancestor of node 13, so no upward move is needed. From node 10, move R to its right child, node 12, and then L to node 13, the left child of node 12.

Constraints

0 <= order <= 43
0 <= fromNode, toNode < size(order), where size(0) = size(1) = 1 and size(n) = 1 + size(n - 2) + size(n - 1).
size(43) = 1402817465, so every node number fits in a signed 32-bit integer.