Leetcode 297. Serialize and Deserialize Binary Tree
Asked at:
Microsoft
Amazon
Meta
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
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.
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef serialize(root):result = []def preorder(node):if not node:result.append('#')returnresult.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).
def deserialize(data):tokens = data.split(',')index = [0]def build():if index[0] >= len(tokens):return Nonetoken = tokens[index[0]]index[0] += 1if token == '#':return Nonenode = TreeNode(int(token))node.left = build()node.right = build()return nodereturn 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.
class Codec:def serialize(self, root):result = []def preorder(node):if not node:result.append('#')returnresult.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 Nonetoken = tokens[index[0]]index[0] += 1if token == '#':return Nonenode = TreeNode(int(token))node.left = build()node.right = build()return nodereturn 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
Problems to Practice
medium
Related problem that helps practice similar concepts and patterns.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Mid February, 2026
Microsoft
Senior
internal interview
Early October, 2025
Amazon
Mid-level
Early August, 2025
Meta
Manager
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.