Lesson 16.5 · Binary Trees
Building Trees from Traversals
Pre-order gives you the root first; in-order tells you which values are in the left and right subtrees. Together they rebuild the tree.
12 min
Think of it like this
Rebuilding a family tree from two lists: one names each parent before their children, the other lists everyone left to right. The first list tells you who's in charge; the second tells you who belongs to which side.
1.Divide by the root
The first pre-order value is the root. Find it in the in-order list: everything left of it forms the left subtree, everything right forms the right subtree, and the subtree sizes tell you how to split the rest of the pre-order list. A HashMap from value to in-order index makes each lookup O(1), so building is O(n).
Remember
- Pre-order[0] is the root.
- Its position in in-order splits the subtrees.
- Index map → O(n).
Common mistakes
- Searching the in-order list linearly each time (O(n²)).
- Assuming duplicates are allowed (the method needs distinct values).