roadmap/trees/Serialize and Deserialize Binary Tree

Serialize and Deserialize Binary Tree

HardFacebookAmazonGoogleMicrosoftBloomberg

Problem

Design an algorithm to serialize a binary tree to a string and deserialize that string back to the original tree.

Intuition — the key insight

Use preorder traversal (root → left → right). Null nodes are encoded as 'N'. This preserves structure uniquely — given preorder with null markers, we can reconstruct the exact tree.

Approach

Preorder with null markers

Serialize: preorder DFS, append val or 'N' for null, comma-separated. Deserialize: split by comma, use an index pointer. For each value: if 'N', return None. Otherwise create node, recurse left, recurse right.

Complexity

Time

O(n)

Space

O(n)

Visit every node. String length proportional to node count.

Solution code

Python

def serialize(self, root) -> str:
    vals = []
    def preorder(node):
        if not node:
            vals.append('N')
            return
        vals.append(str(node.val))
        preorder(node.left)
        preorder(node.right)
    preorder(root)
    return ','.join(vals)

def deserialize(self, data: str):
    vals = iter(data.split(','))
    def build():
        val = next(vals)
        if val == 'N': return None
        node = TreeNode(int(val))
        node.left  = build()
        node.right = build()
        return node
    return build()

Edge cases to remember

⚠Empty tree: serializes to 'N'

⚠Single node: 'val,N,N'

⚠Using an iterator for deserialization avoids index management

Hints

What pattern do you think this problem uses?