Rebuild the Escape Room Clues
An escape room runs on numbered clue cards. Solving a card opens at most two more: a left card and a right card. The owner kept the layout as a binary tree in a file, and the file is now corrupted. Two printouts survived.
The first printout lists the cards in "card first, then everything on its left, then everything on its right" order. The second lists them in "everything on the left, then the card, then everything on the right" order. The owner wants the tree back exactly as it was.
Your task
Write rebuildTree(preorder, inorder). preorder is the pre-order traversal of a binary tree (node, left subtree, right subtree) and inorder is its in-order traversal (left subtree, node, right subtree). Build the tree and return its root.
All card numbers are different, and both lists always come from the same tree, so the answer is unique. The tree is not a search tree. Empty lists mean an empty tree. Return the root as a real TreeNode. Results are shown in level order, with null for a missing child.
rebuildTree(preorder: int[], inorder: int[]) → TreeNode
Examples
preorder = [4, 7, 2, 1, 6] inorder = [7, 2, 4, 6, 1]
[4, 7, 1, null, 2, 6]
The pre-order list starts with 4, so 4 is the first card. In the in-order list, 7 and 2 come before 4 (its left side) and 6 and 1 come after (its right side). Repeat on each side: on the left, pre-order says 7 comes first and in-order puts 2 after 7, so 2 is 7's right card. On the right, 1 comes first and 6 is before it, so 6 is 1's left card.
preorder = [1, 2] inorder = [1, 2]
[1, null, 2]
Pre-order alone says 1 then 2, which fits 2 being on either side. In-order puts nothing before 1, so 1's left side is empty and 2 must be its right card.
Constraints
- 0 ≤ preorder.length = inorder.length ≤ 1,000
- -100,000 ≤ card number ≤ 100,000, all different
- Both lists hold the same numbers and describe one valid tree.
- The tree is at most 500 levels deep.
Start with brute force
The direct recursion takes the root from the front of pre-order, scans the in-order list to find it, then slices both lists into new left and right lists and recurses on the copies.
The idea is right, but every level scans and copies lists. For a tree that is one long chain of 1,000 cards, each step copies almost the whole list again: about 1,000 + 999 + … + 1 ≈ 500,000 element copies, which is O(n²). A hash map of positions removes the scans, and working with index ranges instead of slices removes the copies.
Hints
0 of 4 shown- Hint 1
Look only at the first number of the pre-order list. Which card is it, always? Now find that number in the in-order list. What do the numbers to its left and right tell you?
- Hint 2
The first pre-order number is the root. In the in-order list, everything before the root is its left subtree and everything after is its right subtree. You also learn the size of the left subtree.
- Hint 3
Pre-order lists the root, then the whole left subtree, then the whole right subtree. With the left subtree's size, you can cut the pre-order list into those parts and solve each part the same way. How do you find the root's position in the in-order list without scanning it every time?
- Hint 4
Store each value's in-order position in a hash map. Recurse on an in-order range
[lo, hi]while reading pre-order with one shared index that only moves forward: take the next pre-order value as the root, look up its positionm, build the left subtree from[lo, m - 1], then the right from[m + 1, hi]. An empty range is null. The order (left before right) matters, because that is the order pre-order lists them.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Each list carries half the information. Pre-order tells you who is the root of any subtree: whoever comes first. In-order tells you who is on which side of that root. Use them together, one subtree at a time.
Trace preorder = [4, 7, 2, 1, 6], inorder = [7, 2, 4, 6, 1]. Positions in in-order: 7→0, 2→1, 4→2, 6→3, 1→4.
build(0, 4): next pre-order value is 4, at position 2. Left side is range 0..1, right side is 3..4.build(0, 1): next value is 7, at position 0. Left range 0..-1 is empty. Right range is 1..1.build(1, 1): next value is 2, at position 1. Both sides empty, so 2 is a leaf, and it becomes 7's right child.build(3, 4): next value is 1, at position 4. Left range is 3..3, right range 5..4 is empty.build(3, 3): next value is 6, a leaf, and it becomes 1's left child.
The result is [4, 7, 1, null, 2, 6]. Notice that the shared pre-order index never needs to be computed: because the left subtree is built completely before the right one, the index is always pointing at the right root.
function rebuildTree(preorder, inorder) {
const position = new Map(); // value -> index in inorder
inorder.forEach((v, i) => position.set(v, i));
let next = 0; // next unused value in preorder
// Build the subtree whose values are inorder[lo..hi].
function build(lo, hi) {
if (lo > hi) return null;
const value = preorder[next++]; // this subtree's root
const m = position.get(value);
const node = new TreeNode(value, null, null);
node.left = build(lo, m - 1); // left first: pre-order lists it first
node.right = build(m + 1, hi);
return node;
}
return build(0, inorder.length - 1);
}def rebuild_tree(preorder, inorder):
position = {v: i for i, v in enumerate(inorder)} # value -> index in inorder
next_index = 0 # next unused value in preorder
# Build the subtree whose values are inorder[lo..hi].
def build(lo, hi):
nonlocal next_index
if lo > hi:
return None
value = preorder[next_index] # this subtree's root
next_index += 1
m = position[value]
node = TreeNode(value)
node.left = build(lo, m - 1) # left first: pre-order lists it first
node.right = build(m + 1, hi)
return node
return build(0, len(inorder) - 1)Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.