100. Serialize and Deserialize Binary Tree
hardAsked at PlaidDesign serialize/deserialize for a binary tree. Plaid asks this because their merchant-category tree must be snapshot-able for caching and idempotent replay — they need a stable, deterministic serialization that survives round trips.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Plaid loops.
- Glassdoor (2025)— Plaid SWE III onsite — tree-snapshot variant.
- Blind (2026)— Plaid backend platform OA.
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.
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]Example 2
root = [][]Approaches
1. Level order with nulls
BFS-style; include nulls so structure is reconstructible.
- Time
- O(n)
- Space
- O(n)
// Works but produces longer strings.Tradeoff: Larger output; mainstream JSON-style choice for LC display.
2. Preorder with sentinels
Preorder traversal; emit '#' for null. Deserialize by consuming tokens in the same order.
- Time
- O(n)
- Space
- O(n)
function serialize(root) {
const out = [];
function go(n) {
if (!n) { out.push('#'); return; }
out.push(String(n.val));
go(n.left);
go(n.right);
}
go(root);
return out.join(',');
}
function deserialize(data) {
if (!data) return null;
const tokens = data.split(',');
let i = 0;
function go() {
if (i >= tokens.length) return null;
const t = tokens[i++];
if (t === '#') return null;
const node = { val: +t, left: null, right: null };
node.left = go();
node.right = go();
return node;
}
return go();
}Tradeoff: Preorder is deterministic and compact. The '#' sentinel encodes structure (where nulls live), making deserialization unambiguous.
Plaid-specific tips
Plaid grades this on whether the serialization is round-trippable and deterministic. Bonus signal: discuss the trade-off between preorder (compact) and BFS (more readable in logs). Connect to category-tree snapshot/replay — when you ship a tree across services, you need the deserializer to reconstruct the exact shape.
Common mistakes
- Inorder serialization — can't be deserialized without extra info because root is ambiguous.
- Forgetting null sentinels — leaves vs. internal nodes become indistinguishable.
- Using JSON.stringify on a tree with cycles — crashes (LC trees don't have cycles, but production graphs do).
Follow-up questions
An interviewer at Plaid may pivot to one of these next:
- Serialize a BST more compactly (no sentinels needed because inorder + size pinpoints structure).
- Serialize an N-ary tree (LC 428).
- Streaming serialization that supports partial deserialization.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why preorder, not inorder?
Inorder alone doesn't uniquely identify tree shape (different shapes can yield the same inorder when nulls are skipped). Preorder + sentinels makes the reconstruction deterministic.
How does this generalize to category trees with payloads?
Each node serializes its full payload (val + metadata). Sentinels stay the same. The deserializer parses payload tokens in addition to val.