Serialize and Deserialize Binary Tree

Problem

Design a codec that converts a binary tree into a single string (serialize) and reconstructs the exact same tree from that string (deserialize). You are free to choose any string format you like — the only requirement is that deserialize(serialize(root)) returns a tree identical in structure and values to the original.

Implement a class:

• serialize(root) — takes the root of a binary tree, returns a string.
• deserialize(data) — takes a string previously produced by serialize, returns the rebuilt tree’s root.

Examples

Example 1

    1
   / \
  2   3
     / \
    4   5

Input: root = [1,2,3,null,null,4,5] → Output: [1,2,3,null,null,4,5] One valid encoding is the preorder string "1,2,#,#,3,4,#,#,5,#,#"; decoding it reproduces the tree exactly.

Example 2

Input: root = [] → Output: [] The empty tree must round-trip too — e.g. encode it as "#" (or "") and decode that back to None.

Example 3

  1
 /
2

Input: root = [1,2] → Output: [1,2] A left-only child shows why nulls must be recorded: without a marker, "1,2" can’t tell a left child from a right child.

Constraints

• The tree has between 0 and 10⁴ nodes — both directions should run in O(n) and the string should be O(n) characters.
• -1000 <= Node.val <= 1000 — values can be negative and multi-digit, so you need a real delimiter between tokens.

Think about it first

TL;DR

Preorder DFS with explicit # null markers (BFS works equally well) — O(n) time and O(n) space in both directions.

Approach 1 — Naive design: heap-style index encoding

This is a design problem, so there is no classic brute force; the ladder starts at the most literal design. The most literal encoding borrows the array layout of a binary heap: the root sits at index 0, and node i’s children sit at 2i + 1 and 2i + 2. Store each present node as an index:value pair and rebuild by probing indices.

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        parts: list[str] = []

        def walk(node: Optional[TreeNode], idx: int) -> None:
            if not node:
                return
            parts.append(f"{idx}:{node.val}")
            walk(node.left, 2 * idx + 1)
            walk(node.right, 2 * idx + 2)

        walk(root, 0)
        return ",".join(parts)

    def deserialize(self, data: str) -> Optional[TreeNode]:
        if not data:
            return None
        entries: dict[int, int] = {}
        for part in data.split(","):
            idx_s, val_s = part.split(":")
            entries[int(idx_s)] = int(val_s)

        def build(idx: int) -> Optional[TreeNode]:
            if idx not in entries:
                return None
            node = TreeNode(entries[idx])
            node.left = build(2 * idx + 1)
            node.right = build(2 * idx + 2)
            return node

        return build(0)

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

Complexity: the indices themselves are the problem — in a skewed tree of depth d the index reaches ~2^d, so a single token takes Θ(d) digits. Total string size and time are O(n²) in the worst case (plus big-integer arithmetic).

Why the constraints kill it: with 10⁴ nodes in a chain, indices are ~10⁴-bit numbers and the string balloons to megabytes; the O(n) target demands constant-size tokens.

Approach 2 — Preorder DFS with null markers (recursive)

The insight: a traversal loses the shape only because it skips the nulls. Emit a sentinel # for every absent child and preorder becomes prefix-unambiguous: the first token is always the root of the current subtree, so a decoder that consumes tokens left to right and recurses (build node, then left subtree, then right) can never misplace anything. Preorder is the classical root-left-right depth-first ordering.

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        parts: list[str] = []

        def dfs(node: Optional[TreeNode]) -> None:
            if not node:
                parts.append("#")
                return
            parts.append(str(node.val))
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return ",".join(parts)

    def deserialize(self, data: str) -> Optional[TreeNode]:
        tokens = iter(data.split(","))

        def build() -> Optional[TreeNode]:
            token = next(tokens)
            if token == "#":
                return None
            node = TreeNode(int(token))
            node.left = build()
            node.right = build()
            return node

        return build()

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

Walkthrough on Example 1, [1,2,3,null,null,4,5]:

Serialize visits root-left-right, appending: 1, 2, # (2’s left), # (2’s right), 3, 4, #, #, 5, #, # → "1,2,#,#,3,4,#,#,5,#,#".

Deserialize consumes the same stream: 1 becomes the root and recurses left; 2 becomes its left child, whose two # tokens end that branch; back at the root’s right, 3 is built, then 4 (closed by #,#) as its left child and 5 (closed by #,#) as its right. Every token is consumed exactly once and the original tree reappears.

Complexity: O(n) time and O(n) output both ways (n nodes plus n + 1 null markers); O(h) auxiliary space for the recursion stack, O(n) on a skewed tree.

Approach 3 — BFS level order with null markers (iterative)

The insight: the same null-marker idea works breadth-first — this is essentially LeetCode’s own bracket format. Serialize with a queue (classical BFS: visit nodes level by level), emitting # for missing children; deserialize by walking the token list with a queue of nodes still awaiting children, attaching two tokens per dequeued node. This is the natural pick when recursion depth is a worry, since it needs no call stack at all.

from collections import deque
from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        if not root:
            return ""
        parts: list[str] = []
        queue = deque([root])
        while queue:
            node = queue.popleft()
            if node:
                parts.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                parts.append("#")
        return ",".join(parts)

    def deserialize(self, data: str) -> Optional[TreeNode]:
        if not data:
            return None
        vals = data.split(",")
        root = TreeNode(int(vals[0]))
        queue = deque([root])
        i = 1
        while queue:
            node = queue.popleft()
            if vals[i] != "#":
                node.left = TreeNode(int(vals[i]))
                queue.append(node.left)
            i += 1
            if vals[i] != "#":
                node.right = TreeNode(int(vals[i]))
                queue.append(node.right)
            i += 1
        return root

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

Walkthrough on Example 1: the queue processes 1, then 2, then 3, then 2’s two null children, then 4 and 5, then their nulls, producing "1,2,3,#,#,4,5,#,#,#,#". Deserialize builds 1, dequeues it and attaches 2 and 3 from the next two tokens, dequeues 2 and reads #,# (no children), dequeues 3 and attaches 4 and 5, then closes 4 and 5 with the remaining # tokens.

Complexity: O(n) time and O(n) space both ways; the queue holds at most one level, O(n) worst case.

Common pitfalls

• Omitting the null markers. Preorder values alone are ambiguous — [1,2] with a left child and [1,2] with a right child serialize identically. The sentinels are the shape.
• Reconstructing from preorder + inorder instead. That classic trick fails here because node values may repeat; sentinels avoid relying on values at all.
• Skipping the delimiter. Values are negative and multi-digit (-1000..1000), so "".join output cannot be re-tokenized; always join with "," and split on it.
• Breaking the empty-tree round trip. Whatever serialize(None) returns ("" here, "#" in the DFS version), deserialize must map exactly that back to None — test the pair together.
• Recursion depth in the DFS codec. A 10⁴-node chain can hit CPython’s default recursion limit; raise it with sys.setrecursionlimit or use the BFS codec.

Pattern takeaway

To serialize any recursive structure, pick one fixed traversal order and make the shape explicit with sentinel tokens for the missing branches; deserialization is then the same traversal run in reverse, consuming one token per step from a stream. The reusable pair is “encoder appends in order X” plus “decoder consumes in order X” — with an iterator for DFS or a queue for BFS — and it transfers directly to problems like Serialize BST and Encode N-ary Tree.