Serialize and Deserialize a Binary Tree with BFS
Encode a binary tree to a string and rebuild it exactly, using level-order BFS with null sentinels — intuition, JavaScript code, a worked trace, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
A binary tree lives in memory as a web of pointers. To send it over a network, write it to a file, or cache it in a string column, you have to flatten that web into a single line of text — and then rebuild the exact same shape on the other end. That round trip is what "serialize and deserialize" means.
The catch is shape. Two different trees can hold the same set of values, so a bare list of numbers is not enough. The real problem is encoding structure — which child is missing, which branch is empty — so the decoder can reconstruct the original pointer-for-pointer.
The clean answer is level-order traversal (BFS) with explicit null markers. It gives a symmetric pair of functions: BFS writes the tree out, and the same BFS reads it back.
The problem
Design two functions. serialize(root) turns a binary tree into a string. deserialize(data) turns that string back into a tree identical to the original. The only contract is that deserialize(serialize(root)) reproduces the tree exactly — the encoding format itself is your choice.
Input tree:
1
/ \
2 3
/ \
4 5
serialize(root) -> "1,2,3,null,null,4,5,null,null,null,null"
deserialize(...) -> the same tree, rebuilt node by nodeNode 2 has no children, so its two child slots become null. Node 3 has both, so its slots hold 4 and 5. Those null tokens are the whole trick — they record where the gaps are so structure survives the flattening.
The brute force baseline
The tempting shortcut is to dump the values in level order and skip the empty slots:
function serializeLossy(root) {
const out = [];
const queue = [root];
while (queue.length > 0) {
const node = queue.shift();
if (!node) continue; // silently drop empty slots
out.push(node.val);
queue.push(node.left);
queue.push(node.right);
}
return out.join(",");
}It runs fine and produces short strings. It is also unrecoverable. Consider these two different trees:
1 1
/ \
2 2Both serialize to "1,2". Once the gaps are gone, the decoder cannot tell whether 2 was a left child or a right child — the mapping from tree to string is no longer one-to-one. The problem is not speed; it is that the encoding is lossy. Any correct solution has to spend a little extra space recording the empty positions.
The key insight
Keep the null markers, and make BFS the single ordering rule for both directions.
In level-order traversal you process nodes front-to-back in a queue, always enqueuing a node's left child then its right child. Because that order is deterministic, the decoder can replay it. It reads the first value as the root, then reads values in pairs — each pair is the left and right child of the next parent waiting in its own queue.
The null tokens keep the two queues in lockstep. When the encoder hit an empty child it wrote null; when the decoder reads null, it attaches no child and enqueues nothing. Same order out, same order in. The encoding becomes a bijection, so the round trip is exact.
The optimal solution
This is the algorithm the visualizer steps through — BFS in both directions, with a queue driving each pass.
// Serialization
function serialize(root) {
if (!root) return "";
const queue = [root];
const res = [];
while (queue.length > 0) {
const node = queue.shift();
if (node) {
res.push(node.val.toString());
queue.push(node.left);
queue.push(node.right);
} else {
res.push("null");
}
}
return res.join(",");
}
// Deserialization
function deserialize(data) {
if (!data) return null;
const values = data.split(",");
const root = new TreeNode(Number(values[0]));
const queue = [root];
let i = 1;
while (queue.length > 0 && i < values.length) {
const node = queue.shift();
if (values[i] !== "null") {
node.left = new TreeNode(Number(values[i]));
queue.push(node.left);
}
i++;
if (values[i] !== "null") {
node.right = new TreeNode(Number(values[i]));
queue.push(node.right);
}
i++;
}
return root;
}Two symmetries make this click. On the way out, every dequeued real node emits its value and enqueues both children (even null ones). On the way back, every dequeued node consumes exactly two array slots — one for its left child, one for its right — advancing i twice per parent. Real children get created and pushed onto the queue so their own children get read later; null slots are skipped. Parents are always processed before children because the queue is FIFO, which is precisely why BFS order is reversible.
Walkthrough
Serializing the tree from the problem — root 1, its children 2 and 3, and 3's children 4 and 5. The ∅ symbol marks a null child sitting in the queue.
| Dequeued | res.push | Queue after |
|---|---|---|
| 1 | "1" | [2, 3] |
| 2 | "2" | [3, ∅, ∅] |
| 3 | "3" | [∅, ∅, 4, 5] |
| ∅ | "null" | [∅, 4, 5] |
| ∅ | "null" | [4, 5] |
| 4 | "4" | [5, ∅, ∅] |
| 5 | "5" | [∅, ∅, ∅, ∅] |
| ∅ ×4 | "null" ×4 | [] |
Reading the res column top to bottom gives 1,2,3,null,null,4,5,null,null,null,null. Node 2 contributed the two nulls in the middle (it had no children); node 3 contributed the real 4 and 5. The four trailing nulls are the empty child slots of the leaves 4 and 5 — harmless padding that the decoder simply reads as "no child." (The interactive visualizer trims those trailing nulls for a tidier display, but keeping them costs nothing and the decode still works either way.)
Complexity
Let n be the number of nodes in the tree.
| Operation | Time | Space | Why |
|---|---|---|---|
| serialize | O(n) | O(n) | each node dequeued once; output string holds n values plus up to n+1 null markers |
| deserialize | O(n) | O(n) | each value read once; queue and rebuilt tree both grow to O(n) |
The null markers never more than double the token count — a full binary tree has at most n+1 empty child slots — so the string stays O(n) in length. Every node is enqueued and dequeued exactly once in each direction, giving linear time with no hidden re-scans.
Common mistakes
- Dropping null markers. The
serializeLossybaseline above collapses distinct trees to the same string. Without sentinels the decode is ambiguous — always emitnullfor empty children. - Advancing the index only on real children. In
deserialize,imust increment after both the left check and the right check, even when a slot isnull. Skip an increment and every later parent reads the wrong pair. - Forgetting the empty-tree guard.
serialize(null)should return"", anddeserialize("")should returnnull. Without the early returns,values[0]blows up on an empty input. - Enqueuing null nodes on the decode side. Only push newly created (non-null) children onto the deserialize queue. Pushing a
nullputs a phantom parent in line, and it will greedily consume two array slots that belonged to a real node. - Using
spliton a number-only string without null tokens. If you ever store just values, you lose the ability to place them — the whole point of the sentinels.
Where this pattern shows up next
BFS with a queue and the habit of comparing tree structure carry straight into the rest of the binary-tree family:
- Symmetric Tree — mirror-checking two subtrees, another place where null positions decide the answer.
- Symmetric Tree - Iterative — the same mirror check driven by an explicit queue instead of recursion.
- Same Tree — comparing two trees node-for-node, the exact equality that a correct deserialize must guarantee.
- Subtree of Another Tree — where serialization becomes a shortcut: encode both trees and check for a substring match.
You can also step through the serialize and deserialize visualizer to watch the queue drain and the tree rebuild itself value by value.
FAQ
Why use BFS instead of DFS to serialize a binary tree?
Both work, and DFS preorder with null markers is equally valid. BFS is chosen here because the level-order layout is easy to reason about — the string reads like the tree drawn row by row — and the decode is a simple loop that consumes two slots per parent. DFS solutions typically recurse or carry an explicit index pointer through a preorder stream; they are just as correct but slightly less obvious to trace by hand.
Why do you need null markers in the string?
Because values alone do not capture shape. A tree with 2 as a left child and a tree with 2 as a right child hold the same values but are different trees, and without markers they serialize to the identical string. The null tokens record every empty child position, which is exactly the information needed to make encoding and decoding a one-to-one mapping.
What is the time and space complexity?
Both serialize and deserialize run in O(n) time and O(n) space, where n is the number of nodes. Each node is enqueued and dequeued once per pass, and the serialized string holds n values plus at most n+1 null markers — still linear. The space is dominated by the queue and, for deserialize, the rebuilt tree itself.
Can this handle negative values or an empty tree?
Yes. Values are written with node.val.toString() and parsed back with Number(...), so negatives round-trip correctly as long as your delimiter (a comma here) never appears inside a value. The empty tree is guarded explicitly: serialize(null) returns "" and deserialize("") returns null, so the round trip holds for a tree with zero nodes.
Does the decoder need the same null markers the encoder produced?
It needs enough of them to place every real node, but trailing null markers past the last real node are optional. The deserialize loop stops once i reaches the end of the values array, so extra trailing nulls are simply never read, and trimming them (as the visualizer does for display) changes nothing about the rebuilt tree.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.