Problem 28 · Trees

Serialize and Deserialize Binary Tree

HardClassic DSA & systems

01Problem

Design functions that serialize a binary tree to a string and deserialize that string back into an identical tree.

02Key insight

Pre-order with explicit null markers fully determines the tree; deserialize by consuming tokens from an iterator in the same pre-order.

03Solution

solution.pypython39 lines

from __future__ import annotations
from dataclasses import dataclass
from typing import Iterator, Optional

@dataclass
class TreeNode:
    val: int
    left: Optional[TreeNode] = None
    right: Optional[TreeNode] = None

NULL = "#"

def serialize(root: Optional[TreeNode]) -> str:
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        if node is None:
            out.append(NULL)
            continue
        out.append(str(node.val))
        stack.extend((node.right, node.left))
    return ",".join(out)

def deserialize(data: str) -> Optional[TreeNode]:
    tokens: Iterator[str] = iter(data.split(","))
    first = next(tokens)
    if first == NULL:
        return None
    root = TreeNode(int(first))
    pending = [(root, "right"), (root, "left")]  # child slots in pre-order; no recursion
    while pending:
        parent, side = pending.pop()
        token = next(tokens)
        if token == NULL:
            continue
        child = TreeNode(int(token))
        setattr(parent, side, child)
        pending.extend(((child, "right"), (child, "left")))
    return root

Try it first.

TimeO(n)

SpaceO(n)

tests.py · 5 passing

tests.pypython12 lines

T = TreeNode
root = T(1, T(2), T(3, T(4), T(5)))
assert serialize(root) == "1,2,#,#,3,4,#,#,5,#,#"
assert deserialize(serialize(root)) == root
assert deserialize(serialize(None)) is None
neg = T(-10, None, T(-20))
assert deserialize(serialize(neg)) == neg
deep = None
for v in range(1500):
    deep = T(v, deep)
s = serialize(deep)
assert serialize(deserialize(s)) == s  # 1500-deep skewed tree, no RecursionError

04Staff-level follow-up

Payload size and versioning matter? Use a length-prefixed binary format or protobuf with a schema version; for BSTs drop null markers entirely since pre-order alone plus bounds reconstructs the tree.