Serialize and Deserialize Binary Tree
Description
Serialization is the process of converting a data structure into a sequence of characters (a string) so that it can be stored in a file, sent over a network, or saved in a database. Deserialization is the reverse — taking that string and rebuilding the original data structure from it.
Your task is to design two functions:
- serialize(root): Takes the root of a binary tree and converts it into a string representation.
- deserialize(data): Takes the string produced by serialize and reconstructs the exact same binary tree.
There is no restriction on how your serialization or deserialization algorithm should work. You simply need to ensure that a binary tree can be serialized to a string, and that string can be deserialized back to the original tree structure — preserving every node value, every parent-child relationship, and every null child.
Examples
Example 1
Input: root = [1, 2, 3, null, null, 4, 5]
Output: [1, 2, 3, null, null, 4, 5]
Explanation: The tree looks like this:
1
/ \
2 3
/ \
4 5
Node 1 is the root. Its left child is 2 (which has no children), and its right child is 3. Node 3 has left child 4 and right child 5. After serializing this tree to a string and then deserializing it back, the resulting tree must be identical to the original — same values, same structure, same null children.
Example 2
Input: root = []
Output: []
Explanation: An empty tree (null root) should serialize to some representation of "empty" and deserialize back to null. This is an important edge case — your algorithm must handle the case where there is no tree at all.
Example 3
Input: root = [1]
Output: [1]
Explanation: A single-node tree with value 1. It has no left or right children. Serializing and deserializing should reproduce this single node with both children as null.
Constraints
- The number of nodes in the tree is in the range [0, 10^4]
- -1000 ≤ Node.val ≤ 1000
Editorial
Brute Force
Intuition
When you think about describing a binary tree to someone who cannot see it, the most natural approach is to walk through the tree systematically and record every node you visit. The simplest tree traversal most people learn first is preorder traversal: visit the current node, then its left subtree, then its right subtree.
But here is the catch — if you just record the node values in preorder, you lose information about the tree's shape. For example, the preorder sequence [1, 2, 3] could represent multiple different trees. The key insight is: you must also record where the null (missing) children are. By writing a special marker (like the string "null") every time you encounter a missing child, you fully capture both the values AND the structure of the tree.
For deserialization, you read back the values in the same preorder sequence. If you see a real value, you create a node. If you see the null marker, you know that subtree is empty. Because preorder visits root → left → right, the recursive structure naturally rebuilds the tree.
Step-by-Step Explanation
Let's trace through serialization and deserialization with the tree:
1
/ \
2 3
/ \
4 5
Serialization (Preorder DFS):
Step 1: Visit root node 1. Record "1". Move to left subtree.
Step 2: Visit node 2. Record "2". Move to node 2's left child.
Step 3: Node 2's left child is null. Record "null". Backtrack.
Step 4: Node 2's right child is null. Record "null". Backtrack to node 1.
Step 5: Visit node 3 (right child of 1). Record "3". Move to left subtree.
Step 6: Visit node 4 (left child of 3). Record "4".
Step 7: Node 4's left child is null. Record "null". Backtrack.
Step 8: Node 4's right child is null. Record "null". Backtrack to node 3.
Step 9: Visit node 5 (right child of 3). Record "5".
Step 10: Node 5's left child is null. Record "null".
Step 11: Node 5's right child is null. Record "null".
Serialized string: "1,2,null,null,3,4,null,null,5,null,null"
Deserialization:
Step 1: Read "1" → Create node(1) as root. Recurse for its left child.
Step 2: Read "2" → Create node(2) as left child of 1. Recurse for its left child.
Step 3: Read "null" → Return null (node 2 has no left child). Recurse for node 2's right.
Step 4: Read "null" → Return null (node 2 has no right child). Backtrack.
Step 5: Read "3" → Create node(3) as right child of 1. Recurse for its left child.
Step 6: Read "4" → Create node(4) as left child of 3. Recurse for its left child.
Step 7: Read "null" → Return null. Recurse for node 4's right.
Step 8: Read "null" → Return null. Backtrack.
Step 9: Read "5" → Create node(5) as right child of 3. Recurse for its left child.
Step 10: Read "null" → Return null. Recurse for node 5's right.
Step 11: Read "null" → Return null. Tree fully reconstructed.
Preorder DFS Serialization — Recording Nodes and Nulls — Watch how preorder traversal visits each node (root → left → right) and records null markers for missing children, fully capturing the tree's structure.
Algorithm
Serialize:
- If the current node is null, append "null" to the result and return
- Append the current node's value to the result
- Recursively serialize the left subtree
- Recursively serialize the right subtree
- Join all recorded tokens with a comma delimiter
Deserialize:
- Split the serialized string by commas to get a list of tokens
- Maintain an index pointer starting at 0
- If the current token is "null", increment the pointer and return null
- Otherwise, create a new node with the token's integer value
- Increment the pointer
- Recursively build the left subtree (which advances the pointer through the left subtree's tokens)
- Recursively build the right subtree
- Return the constructed node
Code
class Codec {
public:
// Serialize: preorder DFS with null markers
string serialize(TreeNode* root) {
if (!root) return "null";
return to_string(root->val) + ","
+ serialize(root->left) + ","
+ serialize(root->right);
}
// Deserialize: rebuild from preorder sequence
TreeNode* deserialize(string data) {
queue<string> tokens;
stringstream ss(data);
string token;
while (getline(ss, token, ',')) {
tokens.push(token);
}
return buildTree(tokens);
}
private:
TreeNode* buildTree(queue<string>& tokens) {
string val = tokens.front();
tokens.pop();
if (val == "null") return nullptr;
TreeNode* node = new TreeNode(stoi(val));
node->left = buildTree(tokens);
node->right = buildTree(tokens);
return node;
}
};class Codec:
def serialize(self, root: Optional[TreeNode]) -> str:
"""Preorder DFS serialization with null markers."""
result = []
def dfs(node):
if not node:
result.append("null")
return
result.append(str(node.val))
dfs(node.left)
dfs(node.right)
dfs(root)
return ",".join(result)
def deserialize(self, data: str) -> Optional[TreeNode]:
"""Rebuild tree from preorder sequence."""
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()public class Codec {
// Serialize: preorder DFS with null markers
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serializeHelper(root, sb);
return sb.toString();
}
private void serializeHelper(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append("null,");
return;
}
sb.append(node.val).append(",");
serializeHelper(node.left, sb);
serializeHelper(node.right, sb);
}
// Deserialize: rebuild from preorder sequence
public TreeNode deserialize(String data) {
Queue<String> tokens = new LinkedList<>(Arrays.asList(data.split(",")));
return buildTree(tokens);
}
private TreeNode buildTree(Queue<String> tokens) {
String val = tokens.poll();
if (val.equals("null")) return null;
TreeNode node = new TreeNode(Integer.parseInt(val));
node.left = buildTree(tokens);
node.right = buildTree(tokens);
return node;
}
}Complexity Analysis
Time Complexity: O(n)
Both serialization and deserialization visit every node exactly once. For serialization, the preorder DFS traversal touches each of the n nodes once and appends a constant amount of data. For deserialization, we read each token exactly once and create the corresponding node. Thus, both operations run in O(n) time.
Space Complexity: O(n)
The serialized string stores n node values plus (n+1) null markers, totaling O(n) space. The recursion stack can go as deep as the height of the tree — O(log n) for balanced trees, but O(n) in the worst case for a skewed tree (essentially a linked list). Additionally, during deserialization we store all tokens in a queue of size O(n).
Why This Approach Is Not Efficient
The preorder DFS approach is actually O(n) in time — which is optimal since we must visit every node at least once. However, the recursive approach has a significant practical drawback: the recursion depth equals the tree height, which can be O(n) for highly skewed trees (imagine a tree where every node has only a right child). With n up to 10^4, this could cause a stack overflow on systems with limited stack space.
Additionally, the string concatenation in the C++ recursive serialize function creates new strings at each call, potentially causing O(n²) overhead due to repeated copying (though this can be fixed with a StringBuilder-like approach).
The key question is: can we avoid deep recursion entirely? An iterative approach using a queue (level-order / BFS) naturally avoids this problem — its space usage is proportional to the tree's width, and it never risks stack overflow regardless of tree shape.
Optimal Approach - Level Order BFS
Intuition
Instead of walking the tree depth-first (diving deep before going wide), we can traverse it level by level — this is called Breadth-First Search (BFS) or level-order traversal.
Imagine you are photographing floors of a building from top to bottom. You capture everyone on floor 1 first, then floor 2, then floor 3, and so on. Similarly, BFS visits all nodes at depth 0 (the root), then all at depth 1, then depth 2, etc.
For serialization, we use a queue. We start by enqueuing the root. For each node we dequeue, we record its value and enqueue its children. If a child is null, we record a "null" marker and do not enqueue anything for it.
For deserialization, we reverse the process. We create the root from the first token, enqueue it, and then for each dequeued node we read the next two tokens as its left and right children. If a token is "null", that child is null. Otherwise, we create a new node and enqueue it so its children will be processed later.
This approach is iterative — no recursion means no risk of stack overflow, regardless of tree shape.
Step-by-Step Explanation
Let's trace through both serialization and deserialization with the tree:
1
/ \
2 3
/ \
4 5
Serialization (BFS Level-Order):
Step 1: Initialize a queue with the root node [1]. Result string starts empty.
Step 2: Dequeue node 1. Record "1". Enqueue its left child (2) and right child (3). Queue: [2, 3].
Step 3: Dequeue node 2. Record "2". Node 2's left child is null — record "null" (don't enqueue). Node 2's right child is null — record "null" (don't enqueue). Queue: [3].
Step 4: Dequeue node 3. Record "3". Enqueue its left child (4) and right child (5). Queue: [4, 5].
Step 5: Dequeue node 4. Record "4". Both children null — record "null", "null". Queue: [5].
Step 6: Dequeue node 5. Record "5". Both children null — record "null", "null". Queue: [].
Step 7: Queue is empty. Serialization complete.
Serialized string: "1,2,3,null,null,4,5,null,null,null,null"
Deserialization (BFS Rebuild):
Step 1: Read first token "1". Create root node(1). Enqueue it. Queue: [node(1)].
Step 2: Dequeue node(1). Read next token "2" → create node(2) as left child. Read next token "3" → create node(3) as right child. Enqueue both. Queue: [node(2), node(3)].
Step 3: Dequeue node(2). Read "null" → left child is null. Read "null" → right child is null. Nothing enqueued. Queue: [node(3)].
Step 4: Dequeue node(3). Read "4" → create node(4) as left child. Read "5" → create node(5) as right child. Enqueue both. Queue: [node(4), node(5)].
Step 5: Dequeue node(4). Read "null" → left null. Read "null" → right null. Queue: [node(5)].
Step 6: Dequeue node(5). Read "null" → left null. Read "null" → right null. Queue: [].
Step 7: Queue empty. Tree fully reconstructed — identical to original.
BFS Level-Order Serialization — Queue-Based Tree Encoding — Watch how BFS processes the tree level by level using a queue, recording each node's value and null markers to produce a complete serialized string.
Algorithm
Serialize:
- If root is null, return "null"
- Initialize a queue with the root and an empty result list
- While the queue is not empty:
a. Dequeue a node
b. If the node is null, append "null" to result
c. Otherwise, append the node's value to result, and enqueue its left and right children (even if null) - Join the result list with commas and return
Deserialize:
- Split the string by commas to get tokens
- If the first token is "null", return null
- Create the root node from the first token and enqueue it
- Initialize a token index at 1
- While the queue is not empty:
a. Dequeue a node
b. Read the next token — if not "null", create a left child node and enqueue it; otherwise left child is null
c. Read the next token — if not "null", create a right child node and enqueue it; otherwise right child is null - Return the root
Code
class Codec {
public:
string serialize(TreeNode* root) {
if (!root) return "null";
string result;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (!node) {
result += "null,";
continue;
}
result += to_string(node->val) + ",";
q.push(node->left);
q.push(node->right);
}
// Remove trailing comma
result.pop_back();
return result;
}
TreeNode* deserialize(string data) {
if (data == "null") return nullptr;
vector<string> tokens;
stringstream ss(data);
string token;
while (getline(ss, token, ',')) {
tokens.push_back(token);
}
TreeNode* root = new TreeNode(stoi(tokens[0]));
queue<TreeNode*> q;
q.push(root);
int i = 1;
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
// Left child
if (tokens[i] != "null") {
node->left = new TreeNode(stoi(tokens[i]));
q.push(node->left);
}
i++;
// Right child
if (tokens[i] != "null") {
node->right = new TreeNode(stoi(tokens[i]));
q.push(node->right);
}
i++;
}
return root;
}
};class Codec:
def serialize(self, root: Optional[TreeNode]) -> str:
"""BFS level-order serialization."""
if not root:
return "null"
result = []
queue = deque([root])
while queue:
node = queue.popleft()
if not node:
result.append("null")
continue
result.append(str(node.val))
queue.append(node.left)
queue.append(node.right)
return ",".join(result)
def deserialize(self, data: str) -> Optional[TreeNode]:
"""BFS level-order deserialization."""
if data == "null":
return None
tokens = data.split(",")
root = TreeNode(int(tokens[0]))
queue = deque([root])
i = 1
while queue:
node = queue.popleft()
# Left child
if tokens[i] != "null":
node.left = TreeNode(int(tokens[i]))
queue.append(node.left)
i += 1
# Right child
if tokens[i] != "null":
node.right = TreeNode(int(tokens[i]))
queue.append(node.right)
i += 1
return rootpublic class Codec {
public String serialize(TreeNode root) {
if (root == null) return "null";
StringBuilder sb = new StringBuilder();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node == null) {
sb.append("null,");
continue;
}
sb.append(node.val).append(",");
queue.offer(node.left);
queue.offer(node.right);
}
// Remove trailing comma
sb.deleteCharAt(sb.length() - 1);
return sb.toString();
}
public TreeNode deserialize(String data) {
if (data.equals("null")) return null;
String[] tokens = data.split(",");
TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int i = 1;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
// Left child
if (!tokens[i].equals("null")) {
node.left = new TreeNode(Integer.parseInt(tokens[i]));
queue.offer(node.left);
}
i++;
// Right child
if (!tokens[i].equals("null")) {
node.right = new TreeNode(Integer.parseInt(tokens[i]));
queue.offer(node.right);
}
i++;
}
return root;
}
}Complexity Analysis
Time Complexity: O(n)
Both serialization and deserialization process each node exactly once. Each node is enqueued and dequeued exactly once, and each token is read exactly once during deserialization. The string splitting is also O(n) where n is the total length of the serialized string. Overall: O(n).
Space Complexity: O(n)
The serialized string stores n node values plus null markers, totaling O(n) characters. The queue used during BFS holds at most the width of the tree at any level. For a complete binary tree, the last level can have up to n/2 nodes, so the queue can hold O(n) nodes in the worst case. The tokens array during deserialization also takes O(n) space.
Compared to the DFS approach, BFS avoids the O(n) recursion stack risk for skewed trees. The queue's maximum size depends on tree width (O(n/2) for complete trees) rather than tree height (O(n) for skewed trees with DFS). In practice, BFS is more robust because it is iterative and avoids stack overflow regardless of tree shape.