297. Serialize and Deserialize Binary Tree
Asked at Google, Meta, Amazon, Microsoft and 4 more
Difficulty
Hard
Time
O(n)
Space
O(n)
Pattern
Depth-First Search
Companies
8
Problem
Design two functions that work as a pair. serialize(root) turns a binary tree into a single string. deserialize(data) takes that string back and rebuilds the exact same tree.
The format of the string is up to you. The only hard rule is that the round trip must be lossless: deserialize(serialize(root)) must give back a tree with the same shape and the same values. You may not keep any global state between the two calls — the string is the only thing that travels.
The tricky part is shape. If you only write the node values, the tree structure is lost. So you also need a marker (for example null) for every empty child slot. A common choice is pre-order traversal: write the node, then its left subtree, then its right subtree, using the marker whenever a child is missing.
The round trip must be lossless
Constraints
- ●
The number of nodes in the tree is in the range [0, 10^4]. - ●
-1000 <= Node.val <= 1000 - ●
deserialize(serialize(root)) must reproduce the original tree exactly. - ●
The string is the only channel between the two functions; no shared state is allowed.
Examples
root = [1,2,3,null,null,4,5][1,2,3,null,null,4,5]root = [][]Asked At
8 companies| Company | Difficulty | |
|---|---|---|
| Hard | View all Google questions → | |
| Meta | Hard | View all Meta questions → |
| Amazon | Hard | View all Amazon questions → |
| Microsoft | Hard | View all Microsoft questions → |
| Apple | Hard | View all Apple questions → |
| Netflix | Hard | View all Netflix questions → |
| Uber | Hard | View all Uber questions → |
| Atlassian | Hard | View all Atlassian questions → |
How to Think About It
Pre-order traversal works well: serialize the node value, then left subtree, then right subtree.
Use a special marker (like "null" or "#") for empty nodes. Without markers, you can't reconstruct the tree structure.
On deserialize, use an iterator over the tokens. Read the next token: if "null", return None. Otherwise create a node and recursively build its left and right children.
Why pre-order: it naturally produces tokens in the order you need to reconstruct. The first token is the root, then left subtree tokens, then right subtree tokens.
Edge cases: empty tree (serialize to "null"), single node, skewed tree.
Optimal Approach
serialize(root):
If root is null, return "null".
Return f"{root.val},{serialize(root.left)},{serialize(root.right)}"
deserialize(data):
Split by comma, create iterator.
def build():
val = next(iterator)
if val == "null": return None
node = TreeNode(int(val))
node.left = build()
node.right = build()
return node
return build()
Time: O(n). Space: O(n).
Pre-order with null markers
What Trips People Up in Real Interviews
Not using a marker for null nodes. Without markers, you can't distinguish between different tree structures.
Confusing serialization format with the tree structure. The serialization must be unambiguous — one serialization should produce exactly one tree.
Not using an iterator for deserialization. If you use an index, make sure it's shared across recursive calls (use a mutable object or iterator).
Forgetting to handle null nodes during deserialization. When you read "null", return None and don't recurse.
Using a different traversal order for serialization and deserialization. If you serialize with pre-order, you must deserialize with pre-order. Mixing orders produces the wrong tree.
Solution Code
O(n) timeclass TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Codec:
def serialize(self, root):
if not root:
return "null"
return f"{root.val},{self.serialize(root.left)},{self.serialize(root.right)}"
def deserialize(self, data):
tokens = iter(data.split(","))
def build():
val = next(tokens)
if val == "null":
return None
node = TreeNode(int(val))
node.left = build()
node.right = build()
return node
return build()Frequently Asked Questions
What is the Serialize and Deserialize Binary Tree problem?
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work.
How do you solve Serialize and Deserialize Binary Tree?
The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Serialize and Deserialize Binary Tree?
Serialize and Deserialize Binary Tree is asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Uber, Atlassian. It is a hard difficulty problem.
What are common mistakes on Serialize and Deserialize Binary Tree?
- Not using a marker for `null` nodes. Without markers, you can't distinguish between different tree structures.
- Confusing serialization format with the tree structure. The serialization must be unambiguous — one serialization should produce exactly one tree.
- Not using an iterator for deserialization. If you use an index, make sure it's shared across recursive calls (use a mutable object or iterator).
- Forgetting to handle `null` nodes during deserialization. When you read "`null`", return `None` and don't recurse.
- Using a different traversal order for serialization and deserialization. If you serialize with pre-order, you must deserialize with pre-order. Mixing orders produces the wrong tree.