vault

Serialize and Deserialize Binary Tree

15 min read

Serialize and Deserialize Binary Tree

Serialize = encode a binary tree as a string (or byte sequence); Deserialize = decode that string back into the original tree. The canonical interview answer (LC 297) is pre-order traversal with explicit null markers, which is O(n) time and space in both directions and uniquely determines the tree. A level-order (BFS) variant gives a more “human-readable” encoding (it matches LeetCode’s own input format). For the BST-only variant (LC 449), null markers can be omitted because the BST property is enough to recover the structure during deserialization. Pitfalls cluster around ambiguity (without null markers, two distinct trees can produce the same traversal), parsing efficiency, and Unicode-safe sentinel choice.

1. Intuition — Photographing a Mobile So You Can Rebuild It

A binary tree is like a hanging mobile sculpture: a top piece (root) with up to two arms, each holding another sub-mobile, etc. To ship the mobile to someone, you can’t just write down the names of all the pieces in some unordered list — they’d have no way to know which piece hangs from which arm of which other piece. You need an ordered description that captures the structure.

Pre-order with null markers is “depth-first photography”: at each piece, write down the piece’s name, then recursively describe the left arm’s sub-mobile, then the right arm’s sub-mobile. If an arm is empty, write the special token “(empty)” so the receiver knows to stop descending there. Reading the photo from left to right in the same order, the receiver can rebuild the mobile node-by-node, knowing exactly when to stop and pop back up to a parent.

Level-order is “shelf-by-shelf photography”: describe the top piece first, then both pieces on the second level (left to right), then all four pieces on the third level, etc. Empty slots get null markers too so the receiver can place the children correctly even when some are missing.

2. Tiny Worked Example

Tree:

        1
       / \
      2   3
         / \
        4   5

Pre-order with null markers (using # for null):

1,2,#,#,3,4,#,#,5,#,#

Reading: 1 (root), then “left subtree” — 2 (root of left), # (2’s left empty), # (2’s right empty), back up. Then “right subtree” — 3 (root of right), then 3’s left subtree — 4, #, #, back up. Then 3’s right subtree — 5, #, #. Done.

Level-order with null markers (using # for null):

1,2,3,#,#,4,5,#,#,#,#

Reading shelf by shelf: shelf 0 = [1]; shelf 1 = [2, 3]; shelf 2 = [#, #, 4, 5] (2’s children, then 3’s children); shelf 3 = [#, #, #, #] (4’s children, then 5’s children — all empty, so we can technically stop). The trailing #s are sometimes truncated.

Both encodings uniquely determine the tree. They differ in two ways: (1) pre-order produces a string proportional to the tree’s actual size including null placeholders for absent children, while level-order produces a string proportional to the complete-tree padding of the actual tree (potentially exponential in height for sparse trees, though in practice trimmed); (2) pre-order is deeply recursive, level-order uses a queue.

3. Algorithm — Pre-Order with Null Markers (LC 297 Canonical)

3.1 Why pre-order works for unique reconstruction

Given a pre-order traversal with null markers, deserialization is itself a pre-order recursion in reverse:

  1. Read the next token.
  2. If it’s # (null), return null.
  3. Otherwise create a node with that value. Recursively deserialize the left subtree (reading subsequent tokens). Recursively deserialize the right subtree (reading subsequent tokens).
  4. Return the node.

This works because pre-order’s structure — “root, then full left subtree’s tokens, then full right subtree’s tokens” — gives the deserializer enough information at each recursive call to know exactly where the left subtree’s tokens end and the right’s begin: the recursion itself consumes precisely the tokens belonging to its subtree, leaving the right subtree’s tokens for the next call.

Proof sketch by induction on tree size. Base case: a single # deserializes to null. Inductive step: assume the algorithm correctly reconstructs any tree of fewer than n nodes. For a tree of n nodes with root r, left subtree L (size n_L), right subtree R (size n_R = n − 1 − n_L): the pre-order serialization is r [tokens(L)] [tokens(R)]. Reading r, then recursively deserializing — by the IH the recursion correctly reconstructs L consuming exactly tokens(L) and leaving the parser pointer at the start of tokens(R). The next recursion correctly reconstructs R. Wiring them as the children of r reconstructs the original tree. ∎

3.2 Pseudocode

serialize(root):
    out := []
    function go(node):
        if node is null:
            out.append("#")
            return
        out.append(str(node.val))
        go(node.left)
        go(node.right)
    go(root)
    return ",".join(out)

deserialize(s):
    tokens := iter(s.split(","))
    function go():
        tok := next(tokens)
        if tok == "#":
            return null
        node := new Node(int(tok))
        node.left  := go()
        node.right := go()
        return node
    return go()

3.3 Python implementation

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
class Codec:
    """LC 297. Pre-order DFS with '#' for null."""
 
    def serialize(self, root):
        out = []
        def go(node):
            if node is None:
                out.append("#")
                return
            out.append(str(node.val))
            go(node.left)
            go(node.right)
        go(root)
        return ",".join(out)
 
    def deserialize(self, data):
        tokens = iter(data.split(","))
        def go():
            tok = next(tokens)
            if tok == "#":
                return None
            node = Node(int(tok))
            node.left  = go()
            node.right = go()
            return node
        return go()

The use of an iterator (tokens) lets the recursion advance the read position naturally without manually threading an index through every recursive call. Equivalent index-based formulations exist; the iterator is just sugar.

4. Algorithm — Level-Order (BFS) with Null Markers

LeetCode’s input format [1, 2, 3, null, null, 4, 5] is exactly this — a level-order traversal with null (or #) for missing positions.

4.1 Pseudocode

serialize_bfs(root):
    if root is null: return ""
    out := []
    q := queue([root])
    while q not empty:
        node := q.popleft()
        if node is null:
            out.append("#")
        else:
            out.append(str(node.val))
            q.append(node.left)        # may be null
            q.append(node.right)       # may be null
    return ",".join(out)

deserialize_bfs(s):
    if s is empty: return null
    tokens := s.split(",")
    root := new Node(int(tokens[0]))
    q := queue([root])
    i := 1
    while q not empty and i < len(tokens):
        parent := q.popleft()
        # left child
        if tokens[i] != "#":
            parent.left = new Node(int(tokens[i]))
            q.append(parent.left)
        i += 1
        if i >= len(tokens): break
        # right child
        if tokens[i] != "#":
            parent.right = new Node(int(tokens[i]))
            q.append(parent.right)
        i += 1
    return root

4.2 Python implementation

from collections import deque
 
class CodecBFS:
    def serialize(self, root):
        if root is None:
            return ""
        out = []
        q = deque([root])
        while q:
            node = q.popleft()
            if node is None:
                out.append("#")
            else:
                out.append(str(node.val))
                q.append(node.left)
                q.append(node.right)
        return ",".join(out)
 
    def deserialize(self, data):
        if not data:
            return None
        tokens = data.split(",")
        root = Node(int(tokens[0]))
        q = deque([root])
        i = 1
        while q and i < len(tokens):
            parent = q.popleft()
            if tokens[i] != "#":
                parent.left = Node(int(tokens[i]))
                q.append(parent.left)
            i += 1
            if i >= len(tokens):
                break
            if tokens[i] != "#":
                parent.right = Node(int(tokens[i]))
                q.append(parent.right)
            i += 1
        return root

4.3 Pre-order vs level-order trade-offs

  • Pre-order is more compact for sparse, deep trees because consecutive null markers terminate that subtree’s encoding. A right-skewed tree of n nodes serializes to about 2n + 1 tokens (n values + n+1 nulls).
  • Level-order is more “shape-faithful” — it lays out nodes by depth, matching LeetCode’s input format and being easier for humans to eyeball. But for a sparse tree with deep gaps, level-order can produce many more null markers than pre-order (it must null-pad up to the depth of the deepest node).
  • Both are O(n) time and O(n) space in the standard analyses (where n is the number of real nodes).

5. The BST-Only Variant — Omit Null Markers (LC 449)

For a Binary Search Tree, the BST invariant (left < root < right) gives the deserializer enough information to reconstruct the structure without null markers. Just serialize in pre-order with values only:

serialize_bst(root):
    out := []
    function go(node):
        if node is null: return
        out.append(str(node.val))
        go(node.left); go(node.right)
    go(root)
    return ",".join(out)

To deserialize, walk the pre-order list back into a tree using a bounds-passing recursion (analogous to BST validation in Binary Search Tree §5.1). The root is the first value; the left subtree consists of all subsequent values strictly less than the root; the right subtree consists of all values strictly greater. Because of pre-order’s “root then left-then-right” structure, the left subtree’s values appear first in the pre-order list and end exactly where the first value greater than the root appears.

class CodecBST:
    def serialize(self, root):
        out = []
        def go(node):
            if node is None: return
            out.append(str(node.val))
            go(node.left); go(node.right)
        go(root)
        return ",".join(out)
 
    def deserialize(self, data):
        if not data: return None
        vals = list(map(int, data.split(",")))
        idx = [0]  # mutable index into vals
        def build(lower, upper):
            if idx[0] == len(vals): return None
            v = vals[idx[0]]
            if not (lower < v < upper): return None
            idx[0] += 1
            node = Node(v)
            node.left  = build(lower, v)
            node.right = build(v, upper)
            return node
        return build(float('-inf'), float('inf'))

This achieves smaller serialized output than the general-binary-tree algorithm — for an n-node BST, it’s exactly n integers separated by commas, no # markers needed.

Why this doesn't generalize to non-BST trees

The bounds-recursion above relies on the BST invariant to know “this value belongs to the left subtree iff it’s < root.” A general binary tree has no such invariant; the deserializer can’t tell whether [1, 2, 3] means “root 1, then left subtree 2, then right subtree 3” or “root 1, then left subtree 2-3 (with 3 as 2’s child).” Hence general binary trees require null markers.

6. Why It Works — The Ambiguity Argument

A natural question: why do we need null markers for general binary trees? Why not just serialize the values in some traversal order?

Counterexample. Two different binary trees:

   1                  1
    \                /
     2      vs.     2

Both have the same pre-order traversal ([1, 2]), the same in-order traversal ([1, 2] for the right one, [2, 1] for the left — actually different, OK), the same post-order, and the same level-order. Let me reconsider.

   1                   1
    \                 /
     2               2
      \               \
       3               3

Pre-order of left tree: 1, 2, 3. Pre-order of right tree: 1, 2, 3. Identical. Without null markers, the same string corresponds to multiple distinct trees. With null markers:

  • Left tree: 1, #, 2, #, 3, #, # (root 1, no left, right subtree 2 → 3).
  • Right tree: 1, 2, #, 3, #, #, # (root 1, left 2, 2’s left empty, 2’s right 3, etc.).

Different strings, unambiguous decoding.

This is the root reason every general-binary-tree serialization scheme uses some form of explicit “null” indicator. The two famous “pre-order + in-order ⇒ unique tree” reconstruction trick (LC 105) sidesteps the need for null markers by providing two independent traversals — but that requires the deserializer to be told both, which is more than twice the data of pre-order-plus-nulls in typical cases.

7. Complexity

OperationTimeSpace
Pre-order serializeΘ(n) (write each node + n+1 nulls)Θ(n) output, Θ(h) recursion stack
Pre-order deserializeΘ(n) (one read per token)Θ(n) parsed tokens, Θ(h) recursion stack
Level-order serializeΘ(n) real nodes + null padding (worst case more than n)Θ(n) queue + output
Level-order deserializeΘ(n)Θ(n) queue
BST pre-order serializeΘ(n) (no null markers)Θ(n) output
BST deserialize (bounds recursion)Θ(n)Θ(h)

Why Θ(n) for serialization includes nulls. A binary tree with n real nodes has exactly n + 1 null child slots (each non-null node contributes 2 children, totaling 2n child slots; n − 1 of those are filled by non-root nodes, leaving 2n − (n − 1) = n + 1 null slots). So pre-order with null markers writes 2n + 1 tokens — still Θ(n).

The string-encoding constants matter: "," joins, integer-to-string conversion, etc. all add constant factors. For very large trees, int.to_bytes + custom binary framing can be much faster than str(int) + ","-joined parsing. But for interview-scale n, the obvious Python implementation suffices.

8. Pitfalls

8.1 Forgetting Null Markers

The single most common bug. Without null markers (or some equivalent structural cue), the encoding is ambiguous (§6). Code that “looks correct” on a perfect binary tree silently fails on any tree with single-child nodes. The fix is always to emit a sentinel for absent children.

8.2 Sentinel Collisions With Real Values

If you use # for null but the tree’s nodes can have string values like "#", the deserializer can’t tell them apart. Fixes: choose a sentinel guaranteed not to appear (e.g., empty string "" if values are never empty; or escape real # values; or use length-prefix framing instead of delimiter-split). For integer-valued LeetCode trees the conventional "null" or "#" is fine.

8.3 Comma Inside a Value

Same problem as §8.2 if values contain the delimiter. Length-prefix framing or JSON-style quoting is the production-quality fix.

8.4 Level-Order’s Trailing Nulls

Level-order BFS naturally generates trailing # markers for the last level’s would-be children. These can be trimmed for compactness, but the deserializer must tolerate the absence (typically by exhausting the queue normally; missing children are implicitly null). Mismatched trim/expect logic on the two ends is a frequent bug.

8.5 Recursion Depth on Skewed Trees

The recursive serializer/deserializer is O(h) stack-deep. For a skewed tree with n > 1000, Python’s default limit blows up. Either bump sys.setrecursionlimit or use an iterative implementation with an explicit stack.

8.6 Integer Parsing on Empty Token

Both serializers can produce the empty string (for the empty tree). Deserialize must handle this — int("") raises ValueError. Always check the empty-string case at the entry of deserialize.

8.7 BST Deserialization Bounds Off-By-One

The bounds in build(lower, v) must be strict inequalities matching the strict BST invariant — lower < v < upper. Using <= permits invalid trees and causes the bounds-recursion to consume tokens that don’t belong to the current subtree.

8.8 N-ary Tree Variant

For an n-ary tree, the BFS-with-null-markers pattern still works but the deserializer needs to know the number of children per node (otherwise it can’t tell where one node’s children end and the next sibling’s begin). Solutions: include a per-node child count prefix (val,k,c1,c2,...,ck), or use a per-level sentinel (# separating sibling groups). LC 428 (“Serialize and Deserialize N-ary Tree”) tests this; the canonical solution prefixes each node with its child count.

9. Diagram — Pre-Order Serialization Trace

flowchart TD
    A((1)) --> B((2))
    A --> C((3))
    C --> D((4))
    C --> E((5))

What this diagram shows. The tree being serialized is the example from §2. Pre-order DFS visit sequence (annotated with what gets written):

  1. Visit 1 — write 1. Recurse left.
  2. Visit 2 — write 2. Recurse left → null → write #. Recurse right → null → write #. Pop back to 1.
  3. Recurse right of 1. Visit 3 — write 3. Recurse left.
  4. Visit 4 — write 4, then two #s for its empty children. Pop back to 3.
  5. Recurse right of 3. Visit 5 — write 5, then two #s.
  6. All recursions done.

Final string: 1,2,#,#,3,4,#,#,5,#,#. Note the structural symmetry — every non-null node contributes one value-token followed (somewhere later in the string) by exactly two child-subtree encodings (each of which is itself either # or a recursive expansion). The deserializer mirrors this: pop the next token; if #, return null; otherwise create a node and recursively build its left and right children. The recursion’s stack frames precisely retrace the serialization’s call structure.

10. Real-World Tree Serialization Formats

Beyond LeetCode, tree serialization underpins many real systems:

  • Filesystem dumps — tar, zip, etc. encode directory trees as ordered file streams with explicit directory boundaries (similar to pre-order with null markers).
  • JSON / YAML / XML — natural recursive serialization for any tree-shaped data; nesting brackets serve as the structural cues that null markers do here.
  • Protocol Buffers — for repeated fields containing nested messages, the wire format encodes the count and recursively serializes each child.
  • Git objects — tree objects contain mode + name + sha per child entry; the structural recursion is implicit in the SHA references.
  • Compiler abstract syntax trees — typically pre-order with explicit child counts (n-ary).
  • Database storage of nested document data (e.g., MongoDB BSON) — pre-order recursion with explicit length prefixes.

The general principle: any unambiguous recursive encoding works as long as the decoder can determine, at each step, where one substructure ends and the next begins. Null markers, length prefixes, and matching brackets are the three common techniques.

11. Common Interview Problems

LC #ProblemNotes
297Serialize and Deserialize Binary TreeCanonical pre-order + null markers
449Serialize and Deserialize BSTOmit null markers; use BST property
428Serialize and Deserialize N-ary TreeAdd child-count prefix per node
105Construct Binary Tree from Preorder + InorderTwo-traversal reconstruction (no null markers needed)
106Construct from Inorder + PostorderSame idea, slightly different recursion
889Construct from Preorder + PostorderNote: not unique without extra constraint
652Find Duplicate SubtreesHash subtrees by their serialization
572Subtree of Another TreeCompare by serialization (with null markers!) or recursive structural match

LC 652 is a beautiful application: serialize each subtree (via post-order with null markers) and use a Hash Table to detect duplicates. The null markers are critical here — without them, two structurally distinct subtrees could collide on the same serialization, producing false-positive “duplicates.”

12. Open Questions

  • What’s the most space-efficient unambiguous encoding for a general binary tree of n nodes? Information-theoretically, the lower bound is about 2n bits (one bit per node-or-null position). Pre-order with # markers achieves about this in token count but uses many bytes per token because of integer string-formatting.
  • Does any production system actually use the bounds-recursion BST deserialization, or does everyone just use null markers regardless? The savings are real but small; complexity may not be worth it.
  • How does serialization interact with concurrent tree mutation? Typically the producer takes a snapshot first; lock-free serialization of mutable trees is genuinely hard.

13. See Also

Graph View

Backlinks