Serialize and Deserialize Binary Tree
Problem Statement
Design an algorithm to serialize and deserialize a binary tree. Serialization converts a binary tree into a string. Deserialization converts that string back into the exact same tree structure.
The encoded format is your choice, but it must preserve both node values and missing child positions so the tree can be reconstructed without ambiguity.
Input
For serialize, the input is a TreeNode root. For deserialize, the input is a string produced by the same codec.
Output
For serialize, return a string. For deserialize, return the root of a binary tree whose structure and values match the original tree.
Constraints
- •
0 <= number of nodes <= 10^4 - •
-1000 <= Node.val <= 1000 - •
The tree may be empty - •
Do not rely on shared static state between serialize and deserialize calls
Examples
Example 1
root = [1,2,3,null,null,4,5]
[1,2,3,null,null,4,5]Example 2
root = []
[]Learning Objectives
- Explain why traversal values alone are not enough to preserve arbitrary tree shape.
- Use preorder plus explicit null markers as a complete tree encoding.
- Deserialize by consuming tokens in the same order they were produced.
- Implement a LeetCode-style design class with symmetric serialize and deserialize methods.
Intuition
Pattern Recognition
This is a tree reconstruction problem disguised as a design problem. A traversal like preorder gives visit order, but without missing-child markers, multiple different shapes can produce the same value sequence. The signal is that structure matters as much as values.
Preorder with explicit null markers uniquely determines the tree. Each real token creates a node, then the next tokens fully describe its left subtree and right subtree. Each null token closes one missing child position. Because the stream is consumed in the same recursive order it was written, deserialization does not need a separate inorder traversal.
Common mistakes
- ×Serializing only real node values and losing the shape of missing children.
- ×Using level-order text but forgetting to record enough null positions for sparse trees.
- ×Parsing tokens with a global index that is not reset between calls.
- ×Consuming tokens in a different order during deserialization than the order used during serialization.
Algorithm Explanation
Key idea
Write a preorder DFS stream. For a real node, append its value, then serialize its left subtree, then serialize its right subtree. For a missing child, append the token null. Join tokens with the comma delimiter. To deserialize, put the split tokens in a queue and rebuild recursively by consuming one token per call.
Recursion walkthrough
For [1,2,3,null,null,4,5], preorder visits 1 first. The left child 2 is a leaf, so after 2 the stream records null for its left child and null for its right child. Then the traversal returns to node 1's right child 3. Node 3 writes its left child 4, then two null markers, then its right child 5, then two null markers. During deserialization, token 1 creates the root, the next tokens completely fill its left subtree, and only then do later tokens fill its right subtree.
Algorithm
- For serialization, create an empty token list.
- Run preorder DFS from the root.
- If the current node is null, append null and return.
- Otherwise append the node value, then recurse left, then recurse right.
- Join tokens using the comma delimiter.
- For deserialization, split the data string by comma and store the tokens in a queue.
- Pop one token. If it is null, return null.
- Otherwise create a node with that value, recursively build its left child, recursively build its right child, and return the node.
Solutions
Solution: Preorder DFS with null markers
Use this when the format can be chosen freely. It is compact to implement, easy to reason about, and the serialized stream is self-delimiting because every missing child is represented explicitly.
Serialization and deserialization are exact mirrors. The writer emits one token for every real node and every missing child in preorder. The reader consumes one token at a time from a queue. A null token returns an empty child immediately; a value token creates a node and recursively fills its left and right children.
Step-by-step
- During serialization, append null whenever DFS reaches a missing child.
- Append real node values before visiting children so the stream is preorder.
- Join the token list with commas to produce the final string.
- During deserialization, split by comma and load the tokens into a queue.
- Remove the next token for each recursive call.
- Return null for a null token.
- For a value token, create a node, then recursively assign its left and right children in preorder order.
O(n)
O(n)
Serialization and deserialization each process every real node and null marker once. The token list or queue is O(n), and recursion uses O(h) call-stack space.
Java implementation
Dry Run
Sample input
Serialize and deserialize [1,2,3,null,null,4,5] using preorder tokens: 1,2,null,null,3,4,null,null,5,null,null.
| step | next token or group | action | partial reconstruction |
|---|---|---|---|
| 1 | 1 | create root | node 1 |
| 2 | 2 | create left child of 1 | 1 has left child 2 |
| 3 | null, null | finish both children of 2 | 2 is a leaf |
| 4 | 3 | create right child of 1 | 1 has right child 3 |
| 5 | 4, null, null | create left child of 3 and finish it | 4 is a leaf |
| 6 | 5, null, null | create right child of 3 and finish it | 5 is a leaf |
Every recursive read consumes exactly the tokens written by the matching recursive write. The null markers are what tell the reader when to stop a child branch and return to its parent.
Interview Tips
Clarify that the problem accepts any reversible encoding, then choose preorder with explicit null markers because it is simple and proves uniqueness. Point out that plain preorder without null markers is ambiguous. Keep the implementation symmetric: one helper writes a node, the other helper reads exactly one node or missing child from the queue.
Likely follow-ups
- How would you serialize with level-order traversal instead?
- How would you reduce the output size for a very sparse tree?
- How would you handle values that are strings rather than integers?
- How would you make the codec iterative to avoid deep recursion?
Similar Problems
Key Takeaways
- A tree codec must preserve missing child positions, not just node values.
- Preorder plus explicit **null** markers uniquely describes any binary tree.
- Deserialization should consume tokens in the exact same recursive order used by serialization.
- The codec class should not depend on leftover global state from previous calls.