Serialize and Deserialize Binary Tree — BFS and DFS Approaches

Binary trees live in memory as a web of pointers. The moment your process ends, that web vanishes. Every production system that needs to persist a decision tree, store a parsed expression, cache a DOM snapshot, or ship a hierarchical config over a network needs a way to flatten that tree into bytes and later reconstruct it perfectly. This is not a toy problem — it sits at the heart of databases (B-tree page serialization), compilers (AST persistence), and distributed systems (task-graph checkpointing).

The core challenge is that a flat sequence loses structure. An array of values like [1, 2, 3, 4, 5] could represent dozens of different tree shapes. Serialization must encode both the values AND the structural relationships — specifically, which nodes are absent — so that deserialization can reconstruct the unique tree that produced that sequence, not just any tree containing those values.

By the end of this article you'll have two complete, runnable implementations (BFS-level-order and DFS-preorder), a crystal-clear mental model for why each delimiter and null-marker exists, the performance trade-offs between approaches, and the exact edge cases that silently break naive solutions in production. You'll also be ready to answer every variant of this question an interviewer can throw at you.

What is Serialize and Deserialize Binary Tree? — Plain English

Serialization converts a binary tree into a string (or array) that can be stored in a file or sent over a network. Deserialization reconstructs the exact same tree from that string. The challenge is capturing null children explicitly — without them, you cannot distinguish a node with one child from a complete internal node. For example, trees [1,2] and [1,null,2] have nodes 1 and 2 but completely different shapes. The standard approach marks null children with a sentinel like 'null' and separates values with commas. Two common methods are: BFS (level-order), which mirrors how LeetCode displays trees; and DFS (preorder), which is simpler to implement recursively.

How Serialize/Deserialize Works — Step by Step

Preorder DFS serialization: 1. If node is None, append 'null' to the output and return. 2. Append node.val to the output. 3. Recursively serialize node.left. 4. Recursively serialize node.right. 5. Join with commas: '1,2,null,null,3,null,null'.

Preorder DFS deserialization: 1. Split the string on commas into a queue of tokens. 2. Pop the first token. If it is 'null', return None. 3. Create a node with value = int(token). 4. node.left = recursively deserialize (pops next token). 5. node.right = recursively deserialize (pops next token). 6. Return node.

The key: each recursive call consumes exactly one token (either a value or 'null'). The preorder structure means left and right subtrees are self-contained subsequences.

Worked Example — Serializing and Restoring a Tree

Tree: 1 / \ 2 3 / \ 4 5

Preorder serialization trace: 1. Visit 1: output=['1']. 2. Visit 2 (left of 1): output=['1','2']. 3. Visit null (left of 2): output=['1','2','null']. 4. Visit null (right of 2): output=['1','2','null','null']. 5. Visit 3 (right of 1): output=['1','2','null','null','3']. 6. Visit 4 (left of 3): output=[...,'3','4']. 7. Visit null,null for 4's children: output=[...,'4','null','null']. 8. Visit 5 (right of 3), then nulls: output=[...,'5','null','null']. Final: '1,2,null,null,3,4,null,null,5,null,null'.

Deserialization consumes tokens left to right, building the same tree back. Each 'null' terminates a branch.

Implementation

Preorder serialization uses recursive DFS. Deserialization uses a deque (collections.deque) as a token iterator — popleft() consumes the next token in O(1). The entire tree is processed in O(n) time and O(n) space for the serialized string. BFS serialization using a queue produces the level-order format (useful for display), but DFS is simpler to implement and uses less intermediate state.

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 Codec:
    def serialize(self, root):
        """Preorder DFS → comma-separated string."""
        parts = []
        def dfs(node):
            if node is None:
                parts.append('null')
                return
            parts.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return ','.join(parts)

    def deserialize(self, data):
        """Reconstruct tree from serialized string."""
        tokens = deque(data.split(','))
        def build():
            tok = tokens.popleft()
            if tok == 'null':
                return None
            node = TreeNode(int(tok))
            node.left = build()
            node.right = build()
            return node
        return build()

# Build tree: 1 -> 2, 3 -> 4,5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3, TreeNode(4), TreeNode(5))

codec = Codec()
s = codec.serialize(root)
print(s)  # 1,2,null,null,3,4,null,null,5,null,null

restored = codec.deserialize(s)
print(codec.serialize(restored))  # same string

Frequently Asked Questions