The coding question
A Fibonacci tree of order k is a root with a left subtree of order k-2 and a right subtree of order k-1. Nodes are numbered in preorder. Given the order and a node's number, return the path from the root to that node.
Ask a few questions first
| Ask | What we'll assume |
|---|---|
| What do orders 0 and 1 look like? | Each is a single node with no children. That's where the recursion stops. |
| Where does numbering start? | The root is 0. Preorder means the root, then its whole left subtree, then its whole right subtree. |
| What should the path look like? | A list of node numbers from the root down to the target, both included. |
| How big can the order get? | Big enough that you can't build the tree. Order 80 already has more than 10^16 nodes. |
| What if the node doesn't exist? | Raise an error. |
A couple of examples
| Input | Output |
|---|---|
| order = 4, node = 8 | [0, 4, 6, 8] |
| order = 4, node = 3 | [0, 1, 3] |
| order = 0, node = 0 | [0] |
Start with brute force
Build the whole tree, numbering nodes as you go, then search from the root for the target and keep track of the path.
Cost: O(n) time and memory, where n is the number of nodes. n grows like the Fibonacci numbers, about 1.6 to the power of k, so this dies somewhere around order 40.
A better way
Preorder numbering means every subtree uses one unbroken range of numbers. If a subtree's root is node r and its left subtree has L nodes, the left subtree is r+1 through r+L, and the right subtree starts at r+L+1.
So if you know how big a tree of each order is, you can tell which side the target's on just by comparing numbers. That's the same trick as binary search: look at a range, pick a side, never touch the other one.
The sizes follow their own little recurrence: size(k) = 1 + size(k-2) + size(k-1). Fill them in from the bottom up, a tiny bit of dynamic programming.
- Work out the size of a tree of every order from 0 up to k.
- Start at the root, which is node 0, with the full order k.
- Add the current node to the path. If it's the target, you're done.
- If the target is at most current + size(k-2), go left: the new root is current + 1 and the order drops by 2.
- Otherwise go right: the new root is current + 1 + size(k-2) and the order drops by 1.
The code
def fib_tree_path(order, target):
# sizes[k] = how many nodes a tree of order k has
sizes = [1, 1]
for k in range(2, order + 1):
sizes.append(1 + sizes[k - 2] + sizes[k - 1])
if order < 0 or not 0 <= target < sizes[order]:
raise ValueError("no such node")
path = []
node, k = 0, order # node is the number of the current subtree's root
while True:
path.append(node)
if node == target:
return path
left_size = sizes[k - 2]
if target <= node + left_size:
node, k = node + 1, k - 2 # left subtree starts right after the root
else:
node, k = node + 1 + left_size, k - 1 # right starts after the left
def fib_tree_path_between(order, a, b):
to_a = fib_tree_path(order, a)
to_b = fib_tree_path(order, b)
shared = 0
while shared < min(len(to_a), len(to_b)) and to_a[shared] == to_b[shared]:
shared += 1
# Climb from a up to the last shared node, then down to b.
return to_a[shared - 1:][::-1] + to_b[shared:]| Cost | Why | |
|---|---|---|
| Time | O(k) | The sizes take k steps, and each step down the tree drops the order by at least 1 |
| Memory | O(k) | The sizes list and the path, which is never longer than k + 1 |
Test it
Walk through one of the examples out loud, then check the cases that tend to break things:
- Order 0 or 1, where the only valid node is 0.
- The target is the root, so the path is just [0].
- The last node, which is the deepest right-most one.
- A node number that's too big or negative, which should raise an error.
- A big order like 80, to show you never build anything.
Common mistakes
- Mixing up which side is k-2 and which is k-1. The question says left is k-2.
- Off-by-one when jumping to the right subtree. Don't forget the 1 for the root itself.
- Recomputing subtree sizes with plain recursion, which is exponential. Store them.
- Trying to build the tree because it works for the small examples.
Follow-up questions
How do you find the path between two nodes?
Get both paths from the root. The last node they share is the lowest common ancestor. Climb from the first node up to it, then go down to the second. That's fib_tree_path_between in the code, and it's still O(k).
What if you're given a path and have to return the node's number?
Run the same walk in reverse: start at 0, and for each left step add 1, for each right step add 1 + size(k-2), updating the order as you go.
What if the order is huge, like 10,000?
The sizes become very big numbers. Python handles that, but each addition gets slower. If you only need answers mod some number, or only the directions, you can store less.
How the time adds up
| Minutes | What you're doing |
|---|---|
| 0–5 | Ask questions and agree on examples |
| 5–10 | Talk through the brute force |
| 10–20 | Find the better approach |
| 20–35 | Write the code |
| 35–40 | Test it out loud |
| 40–45 | Follow-up questions |
Key concepts used here
- Trees and recursionSolve tree problems by deciding what each node returns.
- Binary searchCut the search in half, even when you're searching for an answer.
- Dynamic programmingSolve each subproblem once and reuse the answer.
We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Databricks.