Trees · LC #297
Serialize and Deserialize Binary Tree
Design codec to serialize a binary tree to a string and deserialize it back. Preorder DFS with explicit null markers produces a self-describing encoding that can be reconstructed token by token.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Design an algorithm to serialize and deserialize a binary tree. Serialization is the process of converting a data structure into a sequence of bits so that it can be stored in a file or memory buffer. The encoded string should be decoded back to the same tree structure.
Sample I/O
Input: root = [1,2,3,null,null,4,5] Serialized: "1,2,null,null,3,4,null,null,5,null,null" Deserialized: back to same tree
Time: O(n) · Space: O(n)
Intuition
How to Think About It
Intuition
Preorder DFS works for both serialize and deserialize symmetrically: serialize visits root first (easy to record), and deserialize consumes tokens in the same order - first token is always the root, then left subtree tokens, then right subtree tokens. Null markers make the encoding unambiguous, eliminating the need for a second traversal.
Core Concept
Serialize: preorder DFS, append `node.val` or `"null"` with commas. Deserialize: split on commas to get token list, use an index or iterator; each call consumes the next token - if "null" return null, otherwise create node, recurse for left child, recurse for right child.
When to use
Persisting trees to disk/network, caching trees, copying tree structures, interview design problems. Also useful as a building block for subtree hashing.
When NOT to use
When only a specific traversal is needed without round-trip reconstruction (no need for codec). BFS-based serialization is better for shallow wide trees to avoid deep recursion.
Key Insights
What to Know Cold
- Null markers are essential - without them preorder alone can't uniquely identify the tree.
- Preorder serialize + preorder deserialize are perfectly symmetric - same traversal order.
- The token iterator/index is shared across recursive calls - advance it globally.
- BFS serialization (level order with nulls) matches LeetCode's own format.
- The encoded length is exactly 2n+1 tokens for a tree with n nodes (null markers for leaves).
1 example
Worked Examples
Serialize and reconstruct
Tree [1,2,3,null,null,4,5] serialized to comma-separated preorder with nulls.
Serialize: 1→2→null,null→3→4→null,null→5→null,null. Deserialize: consume "1" as root, recurse left consuming "2,null,null", recurse right consuming "3,4,null,null,5,null,null".
class Codec {
serialize(root: TreeNode | null): string {
if (!root) return 'null';
return `${root.val},${this.serialize(root.left)},${this.serialize(root.right)}`;
}
deserialize(data: string): TreeNode | null {
const vals = data.split(',');
let i = 0;
const build = (): TreeNode|null => {
if (vals[i] === 'null') { i++; return null; }
const node = new TreeNode(Number(vals[i++]));
node.left = build();
node.right = build();
return node;
};
return build();
}
}Output: Original tree reconstructed identically
The shared index variable `i` is the key - global across all recursive calls.