Tree Serialization and Deserialization

Serialization converts a tree into a string (or byte stream) that can be stored on disk, sent over a network, or cached. Deserialization reconstructs the exact same tree from that string. This is LeetCode 297 and shows up in system design discussions too.

Why serialization matters

Trees are in-memory data structures with pointers. You cannot directly:

• Save a tree to a file or database
• Send a tree over HTTP/gRPC
• Cache a tree in Redis or Memcached
• Compare two trees by their string representations

Serialization solves all of these by converting the tree to a flat format (string, JSON, bytes) that can be reconstructed later.

What makes tree serialization tricky?

Unlike arrays or linked lists, trees have branching structure. You must encode:

1. The value of each node
2. The shape of the tree (which nodes are children of which)
3. Where null children are (to distinguish left-only vs right-only children)

Without null markers, [1, 2] could mean:

  1        1
 /    or    \
2            2

Approach 1: BFS serialization (level-order)

This is the format LeetCode uses to represent trees: "1,2,3,null,null,4,5".

Serialize (tree to string)

Process level by level using a queue. Include null for missing children.

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class CodecBFS:
    def serialize(self, root):
        """Serialize tree to BFS string."""
        if not root:
            return ""

        result = []
        queue = deque([root])

        while queue:
            node = queue.popleft()
            if node:
                result.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                result.append("null")

        # Remove trailing nulls for cleaner output
        while result and result[-1] == "null":
            result.pop()

        return ",".join(result)

Deserialize (string to tree)

Read values one by one, assigning children to each parent in BFS order.

    def deserialize(self, data):
        """Deserialize BFS string to tree."""
        if not data:
            return None

        values = data.split(",")
        root = TreeNode(int(values[0]))
        queue = deque([root])
        i = 1

        while queue and i < len(values):
            node = queue.popleft()

            # Left child
            if i < len(values) and values[i] != "null":
                node.left = TreeNode(int(values[i]))
                queue.append(node.left)
            i += 1

            # Right child
            if i < len(values) and values[i] != "null":
                node.right = TreeNode(int(values[i]))
                queue.append(node.right)
            i += 1

        return root

BFS example walkthrough

# Tree:
#       1
#      / \
#     2   3
#        / \
#       4   5

# Serialize:
# Queue: [1]
# Process 1 → result: ["1"], enqueue left(2), right(3)
# Queue: [2, 3]
# Process 2 → result: ["1","2"], enqueue left(null), right(null)
# Process 3 → result: ["1","2","3"], enqueue left(4), right(5)
# Queue: [null, null, 4, 5]
# Process null → result: ["1","2","3","null"]
# Process null → result: ["1","2","3","null","null"]
# Process 4 → result: [...,"4"], enqueue nulls
# Process 5 → result: [...,"5"], enqueue nulls
# ... remaining are all null, trimmed

# Output: "1,2,3,null,null,4,5"

# Deserialize:
# values: ["1","2","3","null","null","4","5"]
# Root = 1, queue = [1]
# Process 1: left="2"→create, right="3"→create, queue=[2,3]
# Process 2: left="null"→skip, right="null"→skip, queue=[3]
# Process 3: left="4"→create, right="5"→create, queue=[4,5]
# Process 4: i >= len, stop
# Done!

Approach 2: DFS preorder serialization

Use preorder traversal with a special marker (like #) for null nodes.

Serialize

class CodecDFS:
    def serialize(self, root):
        """Serialize tree using preorder DFS."""
        result = []

        def dfs(node):
            if node is None:
                result.append("#")
                return
            result.append(str(node.val))
            dfs(node.left)
            dfs(node.right)

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

Deserialize

    def deserialize(self, data):
        """Deserialize preorder DFS string to tree."""
        if not data:
            return None

        values = iter(data.split(","))

        def dfs():
            val = next(values)
            if val == "#":
                return None
            node = TreeNode(int(val))
            node.left = dfs()
            node.right = dfs()
            return node

        return dfs()

DFS example walkthrough

# Tree:
#       1
#      / \
#     2   3
#        / \
#       4   5

# Serialize (preorder):
# Visit 1 → "1"
# Visit 2 → "2"
# Visit null (2's left) → "#"
# Visit null (2's right) → "#"
# Visit 3 → "3"
# Visit 4 → "4"
# Visit null (4's left) → "#"
# Visit null (4's right) → "#"
# Visit 5 → "5"
# Visit null (5's left) → "#"
# Visit null (5's right) → "#"

# Output: "1,2,#,#,3,4,#,#,5,#,#"

# Deserialize:
# Read "1" → create node 1
#   Read "2" → create node 2 (left of 1)
#     Read "#" → null (left of 2)
#     Read "#" → null (right of 2)
#   Read "3" → create node 3 (right of 1)
#     Read "4" → create node 4 (left of 3)
#       Read "#" → null
#       Read "#" → null
#     Read "5" → create node 5 (right of 3)
#       Read "#" → null
#       Read "#" → null
# Done!

Using Python’s iterator

The DFS deserialization above uses iter() elegantly. Each call to next(values) advances the iterator globally, so recursive calls naturally consume the right elements in sequence.

An alternative using an index:

def deserialize_index(self, data):
    """Deserialize using explicit index."""
    if not data:
        return None

    values = data.split(",")
    idx = [0]

    def dfs():
        if idx[0] >= len(values) or values[idx[0]] == "#":
            idx[0] += 1
            return None
        node = TreeNode(int(values[idx[0]]))
        idx[0] += 1
        node.left = dfs()
        node.right = dfs()
        return node

    return dfs()

Postorder serialization

You can also serialize using postorder, but deserialization is trickier — you need to build the tree in reverse:

class CodecPostorder:
    def serialize(self, root):
        """Serialize using postorder."""
        result = []

        def dfs(node):
            if node is None:
                result.append("#")
                return
            dfs(node.left)
            dfs(node.right)
            result.append(str(node.val))

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

    def deserialize(self, data):
        """Deserialize postorder — read from the end."""
        if not data:
            return None

        values = data.split(",")
        idx = [len(values) - 1]

        def dfs():
            if idx[0] < 0 or values[idx[0]] == "#":
                idx[0] -= 1
                return None
            node = TreeNode(int(values[idx[0]]))
            idx[0] -= 1
            # Build right first, then left (reverse of postorder)
            node.right = dfs()
            node.left = dfs()
            return node

        return dfs()

Comparison of approaches

Feature	BFS	DFS (Preorder)
String length	Shorter (trailing nulls trimmed)	Longer (explicit null markers)
Deserialization	Queue-based, iterative	Recursive, elegant
Implementation	More code	Less code
Human readable	More intuitive (level by level)	Less intuitive
LeetCode format	Yes	No
Memory during serialization	O(w) queue	O(h) stack

For interviews, DFS preorder is simpler to code. For readability, BFS matches how people draw trees.

Handling edge cases

Empty tree

codec = CodecDFS()
assert codec.serialize(None) == "#"  # or ""
assert codec.deserialize("#") is None

Single node

# Tree: just node 5
# DFS:  "5,#,#"
# BFS:  "5"

Negative values

# Tree: -1 with child -2
# Works fine: "-1,-2,#,#,#"

Very deep trees

DFS serialization uses O(h) recursion stack. For very deep trees (h > recursion limit), use an iterative approach:

def serialize_iterative(self, root):
    """Iterative preorder serialization."""
    if not root:
        return "#"

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        if node is None:
            result.append("#")
        else:
            result.append(str(node.val))
            # Push right first so left is processed first
            stack.append(node.right)
            stack.append(node.left)

    return ",".join(result)

Serialization for N-ary trees

For N-ary trees, we need to encode the number of children:

class CodecNary:
    def serialize(self, root):
        """Serialize N-ary tree."""
        result = []

        def dfs(node):
            if node is None:
                return
            result.append(str(node.val))
            result.append(str(len(node.children)))
            for child in node.children:
                dfs(child)

        dfs(root)
        return ",".join(result) if result else ""

    def deserialize(self, data):
        """Deserialize N-ary tree."""
        if not data:
            return None

        values = iter(data.split(","))

        def dfs():
            val = int(next(values))
            num_children = int(next(values))
            node = NaryNode(val)
            node.children = [dfs() for _ in range(num_children)]
            return node

        return dfs()

Real-world serialization formats

JSON tree representation

import json

def to_json(root):
    """Convert tree to JSON-serializable dict."""
    if not root:
        return None
    return {
        "val": root.val,
        "left": to_json(root.left),
        "right": to_json(root.right)
    }

def from_json(data):
    """Build tree from JSON dict."""
    if data is None:
        return None
    node = TreeNode(data["val"])
    node.left = from_json(data["left"])
    node.right = from_json(data["right"])
    return node

# Usage:
tree_json = json.dumps(to_json(root))
# Store in file, send over API, cache in Redis
restored = from_json(json.loads(tree_json))

Protocol Buffer style

def to_bytes(root):
    """Compact binary serialization."""
    import struct
    result = bytearray()

    def dfs(node):
        if node is None:
            result.append(0)  # null marker
            return
        result.append(1)  # non-null marker
        result.extend(struct.pack('i', node.val))  # 4-byte int
        dfs(node.left)
        dfs(node.right)

    dfs(root)
    return bytes(result)

Testing your serialization

The key property: deserialize(serialize(tree)) == tree

def trees_equal(t1, t2):
    """Check if two trees are structurally identical."""
    if not t1 and not t2:
        return True
    if not t1 or not t2:
        return False
    return (t1.val == t2.val and
            trees_equal(t1.left, t2.left) and
            trees_equal(t1.right, t2.right))

# Test
codec = CodecDFS()
original = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))
serialized = codec.serialize(original)
restored = codec.deserialize(serialized)
assert trees_equal(original, restored)
print(f"Serialized: {serialized}")
print("Round-trip successful!")

Practice problems

1. Serialize and Deserialize Binary Tree (LeetCode 297) — The classic
2. Serialize and Deserialize BST (LeetCode 449) — Can skip null markers
3. Serialize and Deserialize N-ary Tree (LeetCode 428) — Encode child count
4. Verify Preorder Serialization (LeetCode 331) — Validate without building
5. Encode N-ary Tree to Binary Tree (LeetCode 431) — Transform before serializing
6. Find Duplicate Subtrees (LeetCode 652) — Serialize subtrees and compare

Key takeaways

• Serialization converts a tree to a flat string; deserialization reconstructs it
• BFS produces the LeetCode-style format; DFS preorder is simpler to code
• Null markers are essential — without them, tree shape is ambiguous
• The DFS approach using an iterator is elegant: each recursive call consumes the next value
• JSON serialization is the most practical for real-world applications
• Always test with the round-trip property: deserialize(serialize(tree)) == tree