Leetcode 297. Serialize and Deserialize Binary Tree

Asked at:

Microsoft

Rubrik

Amazon

DESCRIPTION

Implement two complementary functions to serialize a binary tree into a string representation and deserialize that string back into the original tree structure. The serialization must preserve exact node values and the complete tree structure, including null children, ensuring the process is fully reversible. For example, a tree [1,2,3,null,null,4,5] should serialize to a string and deserialize back to the identical tree.

Input:

root = [1,2,3,null,null,4,5]
     1
    / \
   2   3
      / \
     4   5

Output:

Serialized: "1,2,#,#,3,4,#,#,5,#,#"
Deserialized: Same tree structure as input

Explanation: Using preorder traversal with # as null marker. The string encodes the tree structure completely, allowing perfect reconstruction.

Constraints:

Number of nodes in the tree is in range [0, 10^4]
Node values are integers in range [-1000, 1000]
The serialization format must uniquely represent the tree structure
Deserialization must reconstruct the exact original tree

Understanding the Problem

The challenge is designing a string encoding that captures both node values and structural information (parent-child relationships and null positions). A naive approach might use level-order traversal, but this requires tracking many trailing nulls. The key insight is using preorder DFS with null markers: visit root, left subtree, right subtree, marking nulls explicitly. This creates a compact representation where each subtree is self-contained, making recursive deserialization natural.

Building Intuition

A naive level-order approach serializes level-by-level (BFS), but requires many trailing null markers for incomplete levels, wasting space. A better preorder DFS approach visits nodes in root → left → right order, inserting a marker (like #) for null children. This creates a self-delimiting format where each subtree's boundaries are implicit in the traversal order. For example, 1,2,#,#,3,4,#,#,5,#,# encodes the tree structure: after reading 2, the next two # markers complete its subtree, then we move to 3's subtree.

Tree serialization is fundamental for data persistence (saving trees to disk/database), network transmission (sending trees between services), and caching (storing computed tree structures). This pattern appears in compiler AST serialization, file system representations, and distributed system state synchronization. Understanding reversible encoding teaches how to design self-describing data formats.

Common Pitfalls

Forgetting null markers: Without explicit null markers, deserialization cannot distinguish tree shapes like [1,2] vs [1,null,2] — always mark nulls

Incorrect delimiter choice: Using , as delimiter fails if node values contain commas — choose delimiters not in the value space or escape properly

Off-by-one in deserialization: Forgetting to advance the index/iterator after reading each value causes misalignment — use a pointer or iterator pattern

Not handling empty tree: Forgetting the edge case where root = null should serialize to a single null marker and deserialize back to null

Implementation

Serialization Function (Encode Tree to String)

Implement the serialize function using preorder DFS traversal to convert the tree into a comma-separated string. Visit each node in root → left → right order, appending the node's value to the result. For null nodes, append a special marker (like #) to preserve structural information. This creates a self-delimiting format where each subtree's boundaries are implicit. For example, the tree [1,2,3] becomes "1,2,#,#,3,#,#" where each # marks a null child, allowing unambiguous reconstruction.

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def serialize(root):
    result = []
    def preorder(node):
        if not node:
            result.append('#')
            return
        result.append(str(node.val))
        preorder(node.left)
        preorder(node.right)
    preorder(root)
    return ','.join(result)

Deserialization Function (Decode String to Tree)

Implement the deserialize function that reconstructs the tree from the serialized string produced in Section 1. Split the string by commas into a list of tokens, then use recursive preorder traversal with an index pointer to consume tokens. Read the current token: if it's the null marker #, return null; otherwise, create a node with that value, recursively build its left subtree (consuming tokens), then its right subtree. The preorder format ensures tokens are consumed in the exact order they were written. For example, "1,2,#,#,3,#,#" reconstructs by reading 1 (root), then recursively processing 2,#,# (left subtree), then 3,#,# (right subtree).

Solution

def deserialize(data):
    tokens = data.split(',')
    index = [0]
    
    def build():
        if index[0] >= len(tokens):
            return None
        token = tokens[index[0]]
        index[0] += 1
        if token == '#':
            return None
        node = TreeNode(int(token))
        node.left = build()
        node.right = build()
        return node
    
    return build()

Complete Integration (Codec Class)

Combine the serialization and deserialization functions from Sections 1 and 2 into a unified Codec class that provides a clean interface for tree encoding/decoding. The class encapsulates both operations and manages shared state (like the token index for deserialization). This demonstrates the reversible transformation pattern: deserialize(serialize(tree)) == tree. For example, instantiate codec = Codec(), call data = codec.serialize(root) to encode, then new_root = codec.deserialize(data) to decode, verifying the round-trip produces an identical tree structure.

Solution

class Codec:
    def serialize(self, root):
        result = []
        def preorder(node):
            if not node:
                result.append('#')
                return
            result.append(str(node.val))
            preorder(node.left)
            preorder(node.right)
        preorder(root)
        return ','.join(result)
    
    def deserialize(self, data):
        tokens = data.split(',')
        index = [0]
        def build():
            if index[0] >= len(tokens):
                return None
            token = tokens[index[0]]
            index[0] += 1
            if token == '#':
                return None
            node = TreeNode(int(token))
            node.left = build()
            node.right = build()
            return node
        return build()

What We've Learned

Pattern: Preorder DFS with null markers creates a self-delimiting serialization format where subtree boundaries are implicit in traversal order
Use Case: Essential for tree persistence, network transmission, and caching in compilers, databases, and distributed systems
Technique: Recursive deserialization with index pointer ensures tokens are consumed in exact serialization order for perfect reconstruction
Design: Codec class pattern encapsulates encode/decode operations, demonstrating reversible transformations and clean API design