1Understand
The idea
A preorder traversal tells you the root first; the inorder traversal then splits the remaining values into the left and right subtrees. Recurse on each side, using a dict from value to inorder index so each split is O(1). Serialization is the same idea in reverse: write the traversal with markers for empty children.
Intuition
Preorder tells you the root first; inorder then splits the remaining values into left and right subtrees. Recurse on each side. A dict from value to inorder index makes each split O(1) instead of scanning.
Postorder + inorder is the same idea with the root at the end of the postorder slice. Serialization writes a traversal with null markers so you can parse uniquely later.
The recursive structure of the tree is exactly the recursive structure of the build.
What you will be able to do
- Use one traversal for roots and inorder for splits
- Encode None markers so the tree is unambiguous
When to use it
- Given preorder and inorder (or postorder)
- Serialize / deserialize
- Build a tree from a list or string
2See it
Walkthrough
Build from preorder + inorder
pre=[3,9,20], in=[9,3,20], root is pre[0]; split inorder.
1 / 5
Preorder root = 3. Inorder index of 3 splits left keys from right keys.
Live template
Line 1 active
Complexity: time O(n), space O(n)
Time O(n) with the index map; O(n²) if each split scans inorder. Space O(n) for the map and O(h) recursion. Serialization/deserialization is O(n); choose a format (preorder with nulls) that preserves structure.
Read the walkthrough as text
Build from preorder and inorder. preorder = [3,9,20,15,7], inorder = [9,3,15,20,7].
- Root is
3(first preorder). In inorder, left of3is[9], right is[15,20,7]. - Next preorder chunk of size 1 builds left child
9. - Remaining preorder
[20,15,7]builds the right subtree with root20, and so on.
In code:
idx = {v: i for i, v in enumerate(inorder)}# recurse with preorder bounds and inorder lo/hi
3Recognise it
Kinds of problems (6)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Preorder + inorder
Example. Rebuild tree from preorder and inorder traversals.
How. Next preorder is root; inorder index map splits left/right ranges recursively.
Postorder + inorder
Example. Construct from postorder and inorder.
How. Root is last postorder element; split inorder at root and recurse on subranges.
Serialize / deserialize (preorder with markers)
Example. Encode tree to string and decode back.
How. Pre-order with explicit “null” tokens so shape is recoverable.
Level-order serialization
Example. Serialize by BFS layers with null slots.
How. Enqueue children even when null until trailing nulls trimmed on decode.
Sorted array to balanced BST
Example. Minimal height BST from sorted nums.
How. Same mid-root divide on index ranges, construction without traversal lists.
Build from parent–child descriptions
Example. Given parent array, wire children under each parent.
How. Map value→node; for each i, attach i to parent[i] as left or right by rule or index parity.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Linear root search
Why it happens. Scanning inorder for each root is simple and avoids extra memory.
How it fails. n nodes, each root scans O(n), O(n²) construction times out on 10⁴ nodes.
Fix. Precompute value → inorder index map once; O(1) split per root.
Ambiguous encoding
Why it happens. Serializing only values feels enough if roots imply structure.
How it fails. Preorder "1,2" could be root+left or root+right, decode rebuilds the wrong shape.
Fix. Encode None explicitly so preorder uniquely determines shape.
Wrong build order
Why it happens. Building the right subtree first matches reading preorder left-to-right visually.
How it fails. Consume preorder for right before left, left subtree never gets its roots in order.
Fix. Always build left subtree range first, then right, matching how preorder is consumed.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.