Serialize and Deserialize Binary Tree

Every time a tree leaves memory — saved to disk, sent over a network, cached in Redis — it has to become a flat string of characters, and something on the other side has to turn it back into exactly the same tree. That is what this problem asks you to design. It is rated hard, but the code is short; the difficulty is seeing what information a flat list loses.

The question underneath every version of this problem is: how does the reader know where a subtree ends? Each approach in this lesson is a different answer to that one question.

The problem

Design two functions. serialize(root) turns a binary tree into a string. deserialize(data) turns that string back into a tree with exactly the same shape and values. You choose the format; the only rule is that deserialize(serialize(tree)) must rebuild the original.

      1     / \    2   3     \      4

• One valid design turns this tree into "1,2,#,4,#,#,3,#,#" and back.
• The empty tree must round-trip too: for example, "#" and back to None.

Constraints: 0 ≤ n ≤ 10⁴ nodes, values between −1000 and 1000 (so values can repeat), and the tree may be unbalanced.

Clarifying questions

• Can values repeat? Yes. This rules out any method that finds a node by its value.
• Negative or multi-digit values? Yes. The format needs a separator between values, and the parser must accept a minus sign.
• Any size limit on the string? No, but a compact format is better; O(n) characters is the target.
• Does it need to be human-readable? No, but a readable format is easier to debug — say so.

The key insight

Write down just the preorder values of the tree above: 1, 2, 4, 3. Now draw a different tree: 1 with children 2 and 3, and 4 as the left child of 2. Its preorder is also 1, 2, 4, 3. The list does not say whether 4 hangs left or right of 2, or where 2's subtree stops and 3's begins.

A traversal records the order of nodes but not the boundaries of subtrees. To rebuild a tree, the format must carry that boundary information somehow. There are two classic ways:

• Send a second traversal. Inorder lists the left subtree, then the root, then the right subtree — so finding the root inside the inorder list tells you exactly how big each side is.
• Mark the missing children. Write a marker like # wherever a child is empty. Then every branch visibly ends, and one traversal is enough.

Approach 1: the simple way — preorder plus inorder

Serialise both lists, for example "1,2,4,3;2,4,1,3". To rebuild: the first preorder value is the root. Find it in the inorder list; everything left of it is the left subtree, everything right of it is the right subtree. Recurse on each side.

The figure shows the first split on a second tree: preorder names the root, inorder sizes the two sides. Searching the inorder list for each root is O(n) per node — O(n²) overall, or 10⁸ steps at 10⁴ nodes. A dictionary from value to inorder position fixes that:

1def build_from_traversals(preorder: list[int], inorder: list[int]) -> Optional[TreeNode]:2    """Rebuild a tree with distinct values from its preorder and inorder lists."""3    index_of = {value: i for i, value in enumerate(inorder)}4    next_root = 0                         # next unused position in preorder56    def build(lo: int, hi: int) -> Optional[TreeNode]:7        """Build the subtree whose values are inorder[lo..hi]."""8        nonlocal next_root9        if lo > hi:10            return None11        value = preorder[next_root]12        next_root += 113        mid = index_of[value]             # everything left of mid is the left subtree14        node = TreeNode(value)15        node.left = build(lo, mid - 1)    # must run first: preorder lists left next16        node.right = build(mid + 1, hi)17        return node1819    return build(0, len(inorder) - 1)

On our tree: root 1 sits at inorder position 2, so the left subtree is inorder [2, 4] and the right is [3]. The next preorder value, 2, sits at position 0 of that slice, so 2 has no left child and [4] on its right. That is the original tree.

This runs in O(n) with the map. But it fails this problem's constraints: with repeated values, index_of cannot tell which 5 is the root, and different trees produce the same pair of lists. It also sends every value twice. It is the right answer to the separate problem "construct a tree from preorder and inorder" — which assumes distinct values — and the wrong one here.

Approach 2: preorder with null markers

Walk the tree in preorder. Write each value, and write # for every missing child. The markers end every branch explicitly, so no second list and no uniqueness is needed.

1def serialize(root: Optional[TreeNode]) -> str:2    """Preorder walk that writes '#' for every missing child."""3    parts: list[str] = []45    def walk(node: Optional[TreeNode]) -> None:6        if node is None:7            parts.append("#")             # the marker that ends a branch8            return9        parts.append(str(node.val))10        walk(node.left)11        walk(node.right)1213    walk(root)14    return ",".join(parts)151617def deserialize(data: str) -> Optional[TreeNode]:18    """Read the tokens back in the same preorder."""19    tokens = iter(data.split(","))2021    def build() -> Optional[TreeNode]:22        token = next(tokens)23        if token == "#":24            return None25        node = TreeNode(int(token))26        node.left = build()               # same order serialize wrote them27        node.right = build()28        return node2930    return build()

deserialize mirrors serialize exactly: it reads a token; a # means "no node here"; a value means "make a node, then build its left subtree, then its right". The shared iterator tokens means each call simply takes the next token — no index arithmetic.

Dry run: reading "1,2,#,4,#,#,3,#,#"

Nine tokens for four nodes: every node writes itself once, and a tree with n nodes has exactly n + 1 empty child slots. So the string has 2n + 1 tokens — O(n).

Complexity. Both functions visit each node once: O(n) time. The string is O(n) long, and the recursion uses O(h) stack.

Approach 3: level order with null markers

The same idea works breadth-first, and avoids recursion entirely — useful for a chain of 10⁴ nodes, which is deeper than Python's default recursion limit.

1from collections import deque234def serialize_bfs(root: Optional[TreeNode]) -> str:5    """Level order, with '#' for every missing child."""6    parts: list[str] = []7    queue = deque([root])8    while queue:9        node = queue.popleft()10        if node is None:11            parts.append("#")12            continue13        parts.append(str(node.val))14        queue.append(node.left)15        queue.append(node.right)16    return ",".join(parts)171819def deserialize_bfs(data: str) -> Optional[TreeNode]:20    """Rebuild level by level: each node takes the next two tokens as children."""21    tokens = data.split(",")22    if tokens[0] == "#":23        return None24    root = TreeNode(int(tokens[0]))25    queue = deque([root])26    i = 127    while queue:28        node = queue.popleft()29        if tokens[i] != "#":30            node.left = TreeNode(int(tokens[i]))31            queue.append(node.left)32        if tokens[i + 1] != "#":33            node.right = TreeNode(int(tokens[i + 1]))34            queue.append(node.right)35        i += 236    return root

Our tree becomes "1,2,3,#,4,#,#,#,#". The reader pops nodes in the same order the writer pushed them, and each popped node claims the next two tokens as its children. Same O(n) time and size, O(w) queue space, no recursion.

Edge cases

• Empty tree. Serialises to "#"; both readers return None on it.
• Repeated values. [5, 5] round-trips, because the markers — not the values — carry the shape.
• Negative and multi-digit values. "-12" is one token thanks to the comma separator, and int("-12") parses it.
• A deep chain. The recursive pair hits Python's recursion limit near 1,000 levels; the level-order pair does not.
• Self-test. Serialise, deserialise, serialise again: the two strings must be identical.

Saying it in the interview

Follow-ups

• "The tree is a binary search tree." Preorder alone is enough: rebuild by passing (low, high) bounds down, and a value outside the bounds belongs to an ancestor's other side. No markers, n tokens, O(n).
• "Each node can have any number of children." Write each value followed by its number of children; the reader then knows how many subtrees to build.
• "Make the string as small as possible." Drop the trailing # tokens of the level-order format, or switch to a binary encoding with fixed-width integers and a bitmap for which children exist.