Serialize and Deserialize Binary Tree
Hard · Trees · Explanation and code example
Breadth First Search
How it works
Instead of using DFS, we treat the tree like a queue (level order traversal). BFS visits nodes level by level, so we simply record values in that order:
- If a node exists → record its value and push its children (even if they are
None). - If a node is missing → record
"N"to mark empty spots.
This ensures the structure is preserved, because BFS processes nodes exactly how they appear in the tree layout.
During deserialization, we again use BFS:
- The first value is the root.
- Then for each node in the queue, assign its left and right children from the next values in the list.
This keeps the tree reconstruction aligned with the serialized order.
Steps
Serialize
- If root is
None→ return"N". - Initialize a queue with
root. - While queue is not empty:
- Pop a node.
- If node exists → append its value, push left & right children.
- If node is missing → append
"N".
- Join the list with commas and return.
Deserialize
- Split string into list
vals. - If first value is
"N"→ returnNone. - Create root from first value and push it into a queue.
- Use an
indexto read the next values:- For each node popped from queue:
- If
vals[index]is not"N"→ create left child & push. - Move
index. - Repeat for right child.
- If
- For each node popped from queue:
- Return the root of the rebuilt tree.
Complexity
- Time complexity:
O(n) - Space complexity:
O(n)
Things to watch for
Forgetting to Handle Null Nodes
A common mistake is not encoding null children in the serialized string. Without explicit null markers (like "N"), the tree structure becomes ambiguous during deserialization. Two different trees could produce the same serialized string if nulls are omitted.
Using a Global Index Without Proper State Management
When deserializing with DFS, using a simple integer variable as an index fails because the index must persist across recursive calls. In many languages, primitive integers are passed by value, so the incremented index is lost when returning from recursion. The solution is to use a mutable wrapper (like an array or object) to maintain the index state.
Incorrect Order of Building Left and Right Subtrees
The deserialization must rebuild children in the exact same order they were serialized. If you serialize using preorder (root, left, right), you must deserialize in preorder too. Building the right subtree before the left will produce an incorrect tree structure.
Not Handling Empty Trees
An empty tree (null root) is a valid input that requires special handling. Forgetting to check for this case in both serialization and deserialization leads to null pointer exceptions or incorrect output.
Delimiter Conflicts with Node Values
Using a delimiter that could appear in node values causes parsing errors. For example, if nodes can have negative values and you use - as a delimiter, parsing becomes ambiguous. Using a character that cannot appear in integer values (like ,) avoids this issue.
Python code example
from typing import Optional
from collections import deque
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Codec:
# Encodes a tree to a single string.
def serialize(self, root: Optional[TreeNode]) -> str:
if not root:
return "N"
res = []
queue = deque([root])
while queue:
node = queue.popleft()
if not node:
res.append("N")
else:
res.append(str(node.val))
queue.append(node.left)
queue.append(node.right)
return ",".join(res)
# Decodes your encoded data to tree.
def deserialize(self, data: str) -> Optional[TreeNode]:
vals = data.split(",")
if vals[0] == "N":
return None
root = TreeNode(int(vals[0]))
queue = deque([root])
index = 1
while queue:
node = queue.popleft()
if vals[index] != "N":
node.left = TreeNode(int(vals[index]))
queue.append(node.left)
index += 1
if vals[index] != "N":
node.right = TreeNode(int(vals[index]))
queue.append(node.right)
index += 1
return root
C++ code example
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if (!root) return "N";
string res;
queue<TreeNode*> queue;
queue.push(root);
while (!queue.empty()) {
TreeNode* node = queue.front();
queue.pop();
if (!node) {
res += "N,";
} else {
res += to_string(node->val) + ",";
queue.push(node->left);
queue.push(node->right);
}
}
return res;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
stringstream ss(data);
string val;
getline(ss, val, ',');
if (val == "N") return nullptr;
TreeNode* root = new TreeNode(stoi(val));
queue<TreeNode*> queue;
queue.push(root);
while (getline(ss, val, ',')) {
TreeNode* node = queue.front();
queue.pop();
if (val != "N") {
node->left = new TreeNode(stoi(val));
queue.push(node->left);
}
getline(ss, val, ',');
if (val != "N") {
node->right = new TreeNode(stoi(val));
queue.push(node->right);
}
}
return root;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.