Serialize and Deserialize Binary Tree
Asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Uber, Atlassian
Problem
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work.
Asked At
| 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.
Visual walkthrough for tree: 1
/ \n 2 3
/ \n 4 5
Serialize: "1,2,null,null,3,4,null,null,5,null,null"
Deserialize: read 1 → node(1). Recurse left → read 2 → node(2). Recurse left → null. Recurse right → null. Back to 1. Recurse right → read 3 → node(3). Recurse left → read 4 → node(4). Both children null. Back to 3. Recurse right → read 5 → node(5). Both children null.
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).
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
class 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.