Serialize and Deserialize Binary Tree
The Prompt
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work.
Understanding the Problem
Serialization must capture enough of the tree that deserialization can rebuild it exactly — shape included. A plain preorder list of values is not enough (many trees share it); the missing information is where the null children are.
The classic fix: preorder traversal that also emits a marker (here ∅) for every null. Those markers make the encoding self-delimiting — while decoding, you always know whether the next token is a real node or the end of a branch, so no lengths or indices are needed.
The Interview Flow
Interviewer
How would you design a way to serialize and deserialize a binary tree?
Candidate
I need a traversal method that unambiguously represents the tree structure. An in-order traversal alone is not enough, as it can represent multiple different trees. A pre-order traversal is a good choice.
Interviewer
How would you handle null children in the pre-order traversal?
Candidate
That's the key. I need to explicitly mark null children in my serialized string. For example, using a special character like "#" or "N". So, a pre-order traversal (root, left, right) would append the node's value, then recursively serialize the left child, and then the right child. If a child is null, I append the null marker.
Interviewer
Okay, so you have a serialized string, like "1,2,N,N,3,4,N,N,5,N,N". How do you deserialize it?
Candidate
I can use the same pre-order sequence. I would first split the string by the delimiter to get a list of values. Then I can use a global index or a queue to consume these values one by one. I would write a recursive `build` function. This function takes the next value from my list. If it's the null marker, it returns null. Otherwise, it creates a new node with that value, then recursively calls `build` to create its left child, and then again to create its right child. The order is crucial.
Interviewer
That's a complete and correct approach for both serialization and deserialization using DFS (pre-order). It perfectly reconstructs the original tree. Please implement it.
Why do null markers make preorder reversible?
The invariant during decoding: the token stream is consumed strictly left to right, and each recursive call consumes exactly the tokens of one subtree. Read one token — if ∅, the subtree is empty and the call returns immediately; otherwise create the node, then recursively decode its left subtree and then its right. Because serialization wrote tokens in exactly this order, decode mirrors encode perfectly and the tree is reconstructed uniquely.
Both directions visit every node and every null slot once: O(n) time and O(n) output size, with O(h) recursion depth. BFS with null markers works equally well — the invariant "each token stream position maps to one tree slot" is what matters, not the traversal order.
Pre-order Traversal (DFS) Approach
- **Serialization (`serialize`):**
- Use a recursive DFS function.
- Base case: if the node is null, append a null marker (e.g., "N") and a delimiter to the result string.
- Otherwise, append the node's value and a delimiter.
- Recursively call for the left child.
- Recursively call for the right child.
- **Deserialization (`deserialize`):**
- Split the input data string by the delimiter into a list of values.
- Use a global index or pass the list by reference to a recursive helper.
- **Recursive `build` function:**
- Take the next value from the list.
- If the value is the null marker, return `null`.
- Otherwise, create a new `TreeNode` with the parsed value.
- The next value in the sequence will build the left subtree, so recursively call `build` to set the node's `left` child.
- The value after that will build the right subtree, so recursively call `build` again to set the `right` child.
- Return the created node.
Try it yourself
Write your solution and run it against 3 test cases.
Both serialize and deserialize must be defined; the round-trip must reproduce the tree.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function serialize(root) {
const res = [];
function dfs(node) {
if (!node) {
res.push("N");
return;
}
res.push(String(node.val));
dfs(node.left);
dfs(node.right);
}
dfs(root);
return res.join(",");
}
function deserialize(data) {
const values = data.split(",");
let i = 0;
function dfs() {
if (values[i] === "N") {
i++;
return null;
}
const node = new TreeNode(parseInt(values[i]));
i++;
node.left = dfs();
node.right = dfs();
return node;
}
return dfs();
}Explanation
Serialize the tree [1, 2, 3, null, null, 4, 5] to "1,2,∅,∅,3,4,∅,∅,5,∅,∅", then decode it back token by token.
1Serialize with preorder, emitting ∅ for each null child: 1, 2, ∅, ∅, 3, 4, ∅, ∅, 5, ∅, ∅. The ∅ after 2 records that 2 is a leaf.
2Decode: read 1 → root; read 2 → its left child; read ∅, ∅ → both children of 2 are null, so 2 is a finished leaf. Control returns to 1, whose right child comes from the next token.
3Reading on: 3 becomes the right child of 1; 4 (then ∅, ∅) its left child; 5 (then ∅, ∅) its right. Every token consumed exactly once — the rebuilt tree is identical to the original.
Complexity Analysis
TIME
O(n)
SPACE
O(n)
Finished working through this one?
Mark it complete to track it on your Data Structures path.