Serialize and Deserialize Binary Tree

Hard

Problem

Design serialize(root) → string and deserialize(string) → root so that any binary tree survives the round trip unchanged. You choose the format.

Example 1

Input:  [1, 2, 3, null, null, 4, 5]
Output: deserialize(serialize(root)) gives the same tree

Test cases

Case 1

Input:    [1,2,3,null,null,4,5]
Expected: [1,2,3,null,null,4,5]

Case 2

Input:    []
Expected: []

Case 3

Input:    [-1,0,1]
Expected: [-1,0,1]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Pre-order with null markers

Time O(n)Space O(n)

Write values in pre-order with "#" for null. Reading back in the same order rebuilds the tree uniquely.

function serialize(root) {
const out = [];
const dfs = (n) => {
if (!n) { out.push('#'); return; }
out.push(n.val);
dfs(n.left); dfs(n.right);
};
dfs(root);
return out.join(',');
}
function deserialize(data) {
const vals = data.split(',');
let i = 0;
const build = () => {
const v = vals[i++];
if (v === '#') return null;
const node = new TreeNode(Number(v));
node.left = build();
node.right = build();
return node;
};
return build();
}

BFS level order with nulls (LeetCode’s own format) also works; mention the choice.