Serialize and Deserialize Binary Tree
Turn a binary tree into a string and back with a preorder DFS that writes a marker for every empty child.
Problem Understanding
Serialize and Deserialize Binary Tree: design two functions. serialize turns a binary tree into a string, and deserialize turns that string back into the same tree. The format is up to you; it only has to round-trip.
Example: the tree [1, 2, 3, null, null, 4, 5] serializes, with the method below, to "1,2,#,#,3,4,#,#,5,#,#".
The Intuition: Preorder Plus Null Markers
Preorder (node, left, right) is a natural way to write a tree down, but values alone lose the shape. The fix is to write a marker, #, for every empty child as well. Then:
- Serialize: visit a node, write its value, recurse left, recurse right. An empty child writes
#. - Deserialize: read the tokens back in the same order. A value creates a node; its left child is built from the next tokens, then its right child. A
#returns an empty child.
Because both directions use the same order, each call to build reads exactly the tokens of its own subtree.
Interactive Walkthrough
First the tree is serialized: nodes fill in as preorder writes them, and the token list grows with a # for each empty child. Then the tree is cleared and rebuilt from those tokens, with the token being read marked and each node reappearing where it came from.
Dry Run Table
Deserialize: "1,2,#,#,3,4,#,#,5,#,#"
| Token | Action |
|---|---|
| 1 | create 1, build its left |
| 2 | create 2 as 1's left, build its left |
| # | 2 has no left child |
| # | 2 has no right child; 2 is complete |
| 3 | create 3 as 1's right, build its left |
| 4 | create 4 as 3's left; its two #s follow |
| 5 | create 5 as 3's right; its two #s end the string |
The Solution Template
Preorder DFS with '#' markers, and a recursive rebuild that reads the tokens in the same order.
Serialize and Deserialize Binary Tree Code
1var serialize = function(root) {2 const out = [];3 const dfs = (node) => {4 if (!node) {5 out.push('#');6 return;7 }8 out.push(String(node.val));9 dfs(node.left);10 dfs(node.right);11 };12 dfs(root);13 return out.join(',');14};1516var deserialize = function(data) {17 const tokens = data.split(',');18 let i = 0;19 const build = () => {20 const token = tokens[i++];21 if (token === '#') return null;22 const node = new TreeNode(Number(token));23 node.left = build();24 node.right = build();25 return node;26 };27 return build();28};
Edge Cases & Common Mistakes
- Empty tree: serializes to
"#"and deserializes back tonull. - Negative and multi-digit values: a delimiter between tokens keeps
-12from being read as-1and2. - Dropping the markers: without
#, different trees produce the same string and the rebuild guesses wrong. - Using
str.splitandindexOfrepeatedly: re-scanning the string for each node makes deserialize O(n²); keep one cursor.
Summary
Preorder plus a marker for every empty child is a complete description of a binary tree. Serialize writes it with one DFS, and deserialize reads it back with a DFS in the same order, each call consuming exactly its own subtree's tokens. Both run in O(n).
More practice: DSA interview questions with answers · patterns cheat sheet