Rebuild From Traversals
Trees & BST: lesson 14 of 14
Preorder names the root, inorder says where to cut.
Lesson 14 of 14 · 6 min
Rebuild From Traversals
Step 1 of 7
nodes0/5
preorder
3920157
inorder
9315207
Neither list alone fixes a tree. Together they do — and the work is all in where to cut.
The Idea
Neither list alone determines a tree, but together they do. Preorder hands you the root first. Find that root in the inorder list and everything to its left is the left subtree, everything to its right the right one.
Slice both lists the same way and recurse. The subtree sizes always match.
Real-World Example
Reconstructing a filing cabinet from two inventories: one that lists each drawer before its folders, and one that lists folders in shelf order. The first says which drawer, the second says where it divides.
The Code
class Node:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
def build(pre, ino):
if not pre: return None
root = pre[0] # preorder hands you the root first
k = ino.index(root) # inorder splits the rest into two sides
return Node(root,
build(pre[1:k + 1], ino[:k]), # k nodes belong on the left
build(pre[k + 1:], ino[k + 1:]))
def show(n): return [] if not n else show(n.left) + [n.val] + show(n.right)
tree = build([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])
print(show(tree)) # [9, 3, 15, 20, 7] -- the inorder we were handed
print(tree.right.left.val) # 15Your turn
Put the steps in the right order.
- Take the first value of the preorder slice as this subtree's root
- Recurse on the left slices, then on the right slices
- Cut both lists at that point, left side first
- Find that value in the inorder slice
Mini quiz
1 / 3