Serialize and Deserialize Binary Tree

Design algorithms to serialize a binary tree to a string and deserialize it back to the same structure.

Answers use simple, clear English.

Time: O(n)Space: O(n)

Quick interview answer

BFS or preorder with explicit null markers (e.g., '#'). Encode level-order values joined by commas; decode with a queue reconstructing children in order.

Detailed answer

BFS or preorder with explicit null markers (e.g., '#'). Encode level-order values joined by commas; decode with a queue reconstructing children in order. Must encode nulls or structure is lost for incomplete trees.

Full explanation

Must encode nulls or structure is lost for incomplete trees.

Real example & use case

Persisting an expression AST across a job queue boundary.

Pros & cons

Pros: round-trip fidelity. Cons: string size grows with null markers.

Code example

from collections import deque

def serialize(root) -> str:
    if not root: return 'null'
    q, out = deque([root]), []
    while q:
        n = q.popleft()
        if not n:
            out.append('null')
            continue
        out.append(str(n.val))
        q.append(n.left); q.append(n.right)
    return ','.join(out)

def deserialize(data: str):
    if data == 'null': return None
    vals = data.split(',')
    root = TreeNode(int(vals[0]))
    q = deque([root]); i = 1
    while q:
        node = q.popleft()
        if vals[i] != 'null':
            node.left = TreeNode(int(vals[i])); q.append(node.left)
        i += 1
        if vals[i] != 'null':
            node.right = TreeNode(int(vals[i])); q.append(node.right)
        i += 1
    return root

Practice code · python (view only · no execution)

from collections import deque

def serialize(root) -> str:
    if not root: return 'null'
    q, out = deque([root]), []
    while q:
        n = q.popleft()
        if not n:
            out.append('null')
            continue
        out.append(str(n.val))
        q.append(n.left); q.append(n.right)
    return ','.join(out)

def deserialize(data: str):
    if data == 'null': return None
    vals = data.split(',')
    root = TreeNode(int(vals[0]))
    q = deque([root]); i = 1
    while q:
        node = q.popleft()
        if vals[i] != 'null':
            node.left = TreeNode(int(vals[i])); q.append(node.left)
        i += 1
        if vals[i] != 'null':
            node.right = TreeNode(int(vals[i])); q.append(node.right)
        i += 1
    return root

#tree#bfs