Tree Construction & Serialization

Why one traversal isn't enough

A single traversal sequence, by itself, does not uniquely determine a tree's shape. Given only the preorder sequence [1, 2, 3], you cannot tell whether this is a straight right-leaning chain, a straight left-leaning chain, or a balanced tree with 1 at the root and 2, 3 as children — all three produce the same preorder output. You need a second, structurally different traversal to disambiguate, because what you're really missing is where each subtree ends and the next begins, and preorder alone doesn't encode that.

Inorder is the traversal that supplies this missing information, because — unlike preorder or postorder — it splits the sequence into "everything left of the root" and "everything right of the root" by position. That's precisely why the two classic construction problems both pair a traversal with inorder:

• Preorder + Inorder: preorder's first element is always the current subtree's root; find that value's index in the corresponding inorder slice, and everything to its left is the left subtree's inorder sequence, everything to its right is the right subtree's.
• Postorder + Inorder: symmetric, except postorder's last element is the root, since postorder visits root last.

Preorder + Postorder is a trap. It looks like it should also work, but it doesn't uniquely reconstruct a general binary tree — if a node has only one child, preorder+postorder cannot tell you whether that child is the left or right child, because neither preorder nor postorder distinguishes "single child, left" from "single child, right" the way inorder's positional split does. (It works fine if you're told every node has 0 or 2 children — a "full" binary tree — but not in general.)

The exception: a Binary Search Tree needs only one traversal. Preorder alone is enough to rebuild a BST uniquely, because the BST ordering invariant itself tells you how to split the remaining sequence — every subsequent value less than the root belongs to the left subtree and everything greater belongs to the right, with no need for a second traversal at all. This is a direct, high-leverage consequence of the invariant covered in the Binary Search Trees subtopic, and it's exactly the insight one of this subtopic's problems is built around.

Constructing from two traversals — the pattern

The general algorithm (illustrated here with preorder + inorder; postorder + inorder is the mirror image) is a straightforward divide-and-conquer, structurally identical to the BST-delete "recurse and reconnect" idiom:

Two details matter here: the hash map trades an O(n) linear scan per node for O(1) lookup, taking the overall algorithm from O(n²) to O(n); and the left subtree must be built before the right one, because both recursive calls consume from the same pre_pos pointer in preorder order — building right first would consume the wrong preorder elements for the left subtree.

Serialization strategies

Serialization is the same underlying problem in reverse: encode a tree into a flat, storable/transmittable form (typically a string), such that it can be decoded back into a structurally identical tree. The key realization is that a bare traversal sequence has the same "not uniquely reversible" problem described above — unless you also record where the None children are, which turns a single traversal into enough information to reconstruct the tree with no ambiguity, equivalent to having a second traversal for free.

Preorder with null markers is the simplest and most common approach:

Each # marks a None child, so the deserializer always knows exactly when to stop recursing — no lookahead or bookkeeping about subtree sizes required, unlike the two-traversal construction above.

Level-order with null markers is the BFS equivalent, and it's the format LeetCode itself uses to render tree inputs/outputs ([1,2,3,null,null,4,5]):

Strategy	Structure	Best when
Preorder + null markers	Recursive, compact	Default choice — simplest to implement correctly under time pressure
Level-order + null markers	Iterative, queue-based	You need a breadth-first/by-depth representation, or want to avoid deep recursion on a skewed tree
Preorder only (no markers), BST	Recursive	Only valid for a BST — the ordering invariant substitutes for the markers

Complexity

All construction and serialization strategies above run in O(n) time (with the hash-map optimization for construction) and O(n) space for the output plus O(h) recursion stack (or O(w) queue for the BFS variant).

Common pitfalls

• Assuming values are unique. The hash-map index lookup in the construction algorithm silently breaks if the tree can contain duplicate values — you'd need to fall back to passing index ranges instead of raw values, or another disambiguation strategy.
• Preorder + Postorder without the "full binary tree" guarantee. As covered above, this pairing is fundamentally ambiguous for trees where some node has exactly one child — don't reach for it unless the problem explicitly guarantees every node has 0 or 2 children.
• Forgetting null markers during serialization. Without them, [1,2] (root 1, left child 2) and [1,2] (root 1, right child 2) serialize identically in plain preorder — the structure is lost. This is the most common correctness bug in this subtopic.
• Multi-digit or negative values without a delimiter. If you concatenate values without a separator (e.g., building a raw string instead of joining with ","), 12 and 1,2 become indistinguishable, and a - sign can be misread as a delimiter. Always use an unambiguous delimiter.
• Recursion depth on skewed trees. As with plain traversal, both construction and preorder-based serialization recurse to depth h, which is O(n) on a skewed tree — prefer the level-order/BFS variant if you need to guard against that.