Serialize and Deserialize Binary Tree
Last Updated: March 29, 2026
Understanding the Problem
We need to convert a binary tree into a string (serialize) and then reconstruct the exact same tree from that string (deserialize). The critical word here is "exact." We don't just need a tree with the same values, we need the same structure. Left children must stay on the left, right children on the right, and null children must be preserved.
Why is this harder than it sounds? Consider two different trees that produce the same inorder traversal. If our serialization only captures values without structural information, we can't tell them apart during deserialization. So we need to encode not just the node values but also where the nulls are, because null positions define the tree's shape.
The key insight: if we record null markers (like "null" or "#") during traversal, we capture the complete structure. A preorder traversal with null markers uniquely defines a binary tree, and so does a level-order (BFS) traversal with null markers.
Key Constraints:
0 <= number of nodes <= 10^4— The tree can have up to 10,000 nodes. We need an approach that handles this efficiently, but even O(n^2) would work within time limits. The real challenge is correctness of the serialization format.-1000 <= Node.val <= 1000— Node values can be negative. Our parsing logic must handle negative signs correctly (e.g., "-1000" is a valid value, not a delimiter followed by "1000").- The tree can be empty (0 nodes). Serialize and deserialize must handle null root gracefully.
Approach 1: DFS (Preorder Traversal)
Intuition
The most natural way to think about this: walk the tree in some order, write down what you see, and include markers for "nothing here." Preorder traversal (root, left, right) is the simplest choice because we process the root first, which makes reconstruction straightforward.
Here's the key insight that makes preorder work: if we record null children explicitly, the serialized string contains enough information to reconstruct the tree without any ambiguity. When we later read the string back, we know that the first token is the root, the tokens that follow describe the left subtree (terminated by null markers), and whatever comes after that describes the right subtree.
For serialization, we do a standard preorder DFS. At each node, we append its value. When we hit a null child, we append a special marker like "N". We separate tokens with commas.
For deserialization, we split the string into tokens and consume them one by one. We use a recursive function that reads the next token: if it's "N", return null. Otherwise, create a node with that value, then recursively build its left subtree (which consumes the next chunk of tokens) and its right subtree (which consumes the chunk after that).
A preorder traversal with null markers uniquely identifies a binary tree because it captures both the values and the structure. The null markers tell us exactly where each subtree ends. During deserialization, the recursive structure naturally "consumes" the right number of tokens for each subtree. The left subtree reads tokens until it hits enough null markers to be complete, and then the right subtree picks up where the left one stopped.
Algorithm
Serialize:
- If the current node is null, append "N" to the result and return.
- Append the node's value to the result.
- Recursively serialize the left subtree.
- Recursively serialize the right subtree.
- Join all values with commas to form the final string.
Deserialize:
- Split the serialized string by commas into a list of tokens.
- Maintain an index (or use a queue/iterator) to track which token to process next.
- Read the next token. If it is "N", return null.
- Create a new tree node with the token's integer value.
- Recursively build the left child (this advances the index through the left subtree's tokens).
- Recursively build the right child (this advances the index through the right subtree's tokens).
- Return the constructed node.
Example Walkthrough
Code
- Time Complexity: O(n). Serialization visits every node exactly once. Deserialization processes every token exactly once. With n nodes, there are about 2n+1 tokens total, which is O(n).
- Space Complexity: O(n). The serialized string stores 2n+1 tokens. The recursion stack can go up to O(n) deep in the worst case (a completely skewed tree).
The DFS approach is already O(n) in both time and space, which is optimal. But what if we want an iterative solution that avoids deep recursion stacks? A skewed tree with 10,000 nodes would cause 10,000 recursive calls. BFS naturally avoids this by using a queue instead of the call stack.
Approach 2: BFS (Level-Order Traversal)
Intuition
Instead of traversing depth-first, we can serialize the tree level by level using BFS. This is actually how LeetCode itself represents binary trees in its input format: [1,2,3,null,null,4,5].
The idea is straightforward. We use a queue to visit nodes level by level. For each node we dequeue, we append its value and enqueue its children. If a child is null, we append a null marker but don't enqueue anything for it (null nodes have no children to process).
For deserialization, we reverse the process. The first token is the root. We put it in a queue. Then, for each node we dequeue, the next two tokens in the string are its left and right children. If a token is "N", the child is null. Otherwise, we create a node and enqueue it so its children get processed later.
This approach is iterative, so it avoids the potential stack overflow issue with very deep trees.
The BFS approach works because the level-order traversal creates a natural parent-child pairing. When we serialize, each non-null node contributes exactly two tokens (its left and right children) to the output. During deserialization, we maintain a queue of nodes that still need children assigned. For each node we dequeue, we consume exactly two tokens. This one-to-one correspondence between enqueued nodes and token pairs guarantees correctness.
The null markers are essential because they preserve the tree's shape. Without them, we couldn't distinguish between a node with only a left child versus only a right child.
Algorithm
Serialize:
- If root is null, return an empty string.
- Initialize a queue with the root node.
- While the queue is not empty, dequeue a node.
- If the node is null, append "N" to the result.
- If the node is not null, append its value and enqueue its left and right children (even if they're null).
- Join all values with commas.
Deserialize:
- If the string is empty, return null.
- Split the string by commas into tokens.
- Create the root from the first token and add it to a queue.
- Starting from the second token, process tokens in pairs (left child, right child) for each node dequeued.
- For each token: if "N", set child to null. Otherwise, create a node, set it as child, and enqueue it.
- Return the root.
Example Walkthrough
Code
- Time Complexity: O(n). Both serialization and deserialization visit each node exactly once. Splitting the string and parsing integers are all O(n) operations overall.
- Space Complexity: O(n). The serialized string stores O(n) tokens. The BFS queue holds at most O(n) nodes (in the worst case, the widest level of a complete binary tree is about n/2 nodes).