Pattern 4: Construction and serialization
Up to here we have consumed ready-made trees. Now the inverse problem: building a tree (from traversals or from a string) without ambiguity. It is recursion again — but the insight is in understanding what each traversal reveals.
Try it first: Construct Binary Tree from Preorder and Inorder
Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.
Rebuild the binary tree from its preorder and inorder traversals (no repeated values). Return the root.
Example: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] → [3,9,20,null,null,15,7].
Did you try? The challenge is to find out, at each step, who is the root and where the tree splits into left and right. The theory below shows how preorder and in-order, together, give that information.
Theory 1: rebuilding from traversals
A single traversal is not enough to rebuild the tree (several different trees give the same preorder). But preorder + in-order together uniquely determine the tree. The key is two observations:
- Preorder (node → left → right): the first element is always the root.
- In-order (left → node → right): the root splits the list — everything to its left is the left subtree, everything to its right is the right one.
pre: [3, 9, 20, 15, 7] → root is 3
in: [9, 3, 15, 20, 7] → 9 | 3 | 15,20,7
↑left ↑root ↑right
So: take the root from the preorder, find it in the in-order to learn the size
of each side, and recursively build left and right. Consume the preorder
with a pointer that only advances (it is already in the right order: root, all
of the left, all of the right). A map value → position in the in-order avoids
searches and keeps it O(n).
Theory 2: serialize and deserialize
Serializing is turning the tree into a string; deserializing is rebuilding it exactly. It is the same problem of unambiguous representation you saw in String (encoding) — now applied to the tree's structure.
The cleanest way: preorder with empty markers. Write the node's value and,
for each missing child, a marker (#). This records the complete structure, so
the reconstruction is unique:
1
/ \ → serialize (preorder) → "1,2,#,#,3,#,#"
2 3
On the way back, read the tokens in order: a value creates a node (and
recursively reads its two children); a # is None. Since the preorder places
each node before its children, reading in the same order rebuilds it
perfectly.
Complexity
Both directions visit each node (and each empty marker) once → O(n) time. Serialization produces an O(n) string; deserialization uses the O(h) recursion stack. The reading pointer never goes back — each token is consumed once.
The lesson that connects the sections
Building from traversals and serializing are variations of one idea: the order in which you write/read the nodes must carry the structure without ambiguity. Preorder solves this because it places the root before the children. It is the same principle as the length-prefix from the String section — representing data in a reconstructible way. Patterns travel between sections.
🧠 Review quiz
0/41. Why is a single traversal (just preorder, for example) not enough to rebuild the tree?
2. In the reconstruction with pre + in-order, what does each traversal provide?
3. Why does preorder serialization WITH empty markers (#) rebuild the tree without ambiguity?
4. What principle from another section does tree serialization reuse?
Summary
- Rebuilding from pre + in-order: pre gives the root; in-order splits left/right; recursion builds it. O(n).
- Serializing: preorder with empty markers (
#) records the structure without ambiguity; deserializing reads in the same order. - Same principle as the length-prefix from the String section: reconstructible representation.
Next lesson: a tree specialized in text — the Trie.