297. Serialize and Deserialize Binary Tree
hardAsked at LinearDesign a codec that converts a binary tree to a string and back. Linear asks this to probe system design thinking in a coding context — can you design a self-describing format and implement both encode/decode symmetrically?
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Linear loops.
- Glassdoor (2025-12)— Cited in Linear SWE onsite reports as a design-heavy hard problem for senior-track candidates.
- Blind (2025-11)— Mentioned in Linear interview threads as a problem that bridges coding and system design.
Problem
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. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
Constraints
The number of nodes in the tree is in the range [0, 10^4].-1000 <= Node.val <= 1000
Examples
Example 1
root = [1,2,3,null,null,4,5][1,2,3,null,null,4,5]Explanation: Serialize to a string then deserialize back to the original tree.
Approaches
1. BFS (level-order) serialization
Serialize with BFS, encoding null children as 'null'. Deserialize by reading node values in BFS order and reconstructing the tree level by level.
- Time
- O(n)
- Space
- O(n)
class Codec {
serialize(root) {
if (!root) return 'null';
const result = [];
const q = [root];
while (q.length) {
const node = q.shift();
if (node === null) { result.push('null'); }
else {
result.push(node.val.toString());
q.push(node.left);
q.push(node.right);
}
}
return result.join(',');
}
deserialize(data) {
const vals = data.split(',');
if (vals[0] === 'null') return null;
const root = { val: parseInt(vals[0]), left: null, right: null };
const q = [root];
let i = 1;
while (q.length && i < vals.length) {
const node = q.shift();
if (vals[i] !== 'null') {
node.left = { val: parseInt(vals[i]), left: null, right: null };
q.push(node.left);
}
i++;
if (i < vals.length && vals[i] !== 'null') {
node.right = { val: parseInt(vals[i]), left: null, right: null };
q.push(node.right);
}
i++;
}
return root;
}
}Tradeoff: O(n) time and space. BFS serialization is intuitive and mirrors how many tree representations (like LeetCode input format) work. Easy to explain and implement.
2. DFS preorder serialization
Serialize with preorder DFS (root, left, right), encoding nulls. Deserialize recursively consuming the token stream.
- Time
- O(n)
- Space
- O(n)
class Codec {
serialize(root) {
const parts = [];
function dfs(node) {
if (!node) { parts.push('null'); return; }
parts.push(node.val.toString());
dfs(node.left);
dfs(node.right);
}
dfs(root);
return parts.join(',');
}
deserialize(data) {
const vals = data.split(',');
let idx = 0;
function build() {
if (idx >= vals.length || vals[idx] === 'null') { idx++; return null; }
const node = { val: parseInt(vals[idx++]), left: null, right: null };
node.left = build();
node.right = build();
return node;
}
return build();
}
}Tradeoff: O(n) time and space. Preorder DFS naturally reconstructs the tree in the same traversal order — the root always comes first, allowing recursive deserialization. More compact code than BFS.
Linear-specific tips
Before coding, explain your format design: 'I'll use comma-separated values with the literal string null for missing children. Preorder DFS works because the root always appears first, making recursive deserialization straightforward.' Linear interviewers grade this on format clarity and symmetric codec design as much as correct code.
Common mistakes
- Not encoding null children — without null markers, trees with the same in-order traversal but different shapes are indistinguishable.
- Using a shared mutable index variable in deserialize — a closure over idx or an index object avoids passing index back and forth through recursive returns.
- Forgetting to handle the empty tree — serialize(null) should produce a recognizable empty token, not an empty string.
Follow-up questions
An interviewer at Linear may pivot to one of these next:
- Serialize and Deserialize BST (LC 449) — BSTs can be serialized without null markers since structure is implied by values.
- Encode and Decode Strings (LC 271) — similar encoding problem but for a list of strings.
- How would you design a space-efficient binary format instead of a text-based one?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why must null children be encoded?
Without null markers, the structure is ambiguous. For example, a node with one left child and no right child looks like a node with one right child and no left child if you only record non-null values.
Why is preorder better than inorder for serialization?
Preorder places the root first, enabling top-down reconstruction in the same order. Inorder alone does not uniquely identify a tree structure — you'd need inorder + preorder or postorder.
How does BFS serialization handle skewed trees?
A fully left-skewed tree of depth n produces n null entries for missing right children. This is O(n) space, same asymptotically as DFS, but can produce longer strings in practice.
Practice these live with InterviewChamp.AI
Drill Serialize and Deserialize Binary Tree and other Linear interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →