Serialize and Deserialize Binary Tree
HardTrees
Write two functions. serialize(root) turns a binary tree into a string, in any format you like. deserialize(data) takes that string and rebuilds the same tree, returning its root.
The string must carry the whole tree: the tests build a tree, call serialize, take apart the original tree, then call deserialize on your string and compare what comes back with the tree they started from. Values can be negative and can have several digits.
On this page a tree is written in level order, top to bottom and left to right, with null where a child is missing: [6, 3, 8, 1] is 6 with children 3 and 8, and 3 with a left child 1. The output is the tree deserialize returned, written the same way.
Examples
Input: root = [7, -3, 12, null, 4, 10] Output: [7, -3, 12, null, 4, 10]
Whatever string serialize makes, deserialize must turn it back into this exact tree.
Input: root = [100, null, -25, 8] Output: [100, null, -25, 8]
The root has only a right child, so the string must record the missing left one.
Constraints
- The tree has 0 to 10⁴ nodes.
-1000 ≤ node.val ≤ 1000
Stuck?
Hint 1
A list of the values alone loses the shape. Write a marker for every missing child as well, and the shape can be read back.
Hint 2
Write a preorder walk with a marker such as # for null and commas between the tokens. To rebuild, split on the commas and read the tokens in the same order with one recursive function; splitting keeps negative and many-digit values whole.
The idea
A list of values loses the tree's shape, but a preorder walk that also writes a marker for every missing child keeps it. Read the tokens back in the same order, and the markers tell the rebuild exactly where each subtree ends.
Time O(n) for each functionExtra space O(n)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 6
Write # for a missing child. These markers carry the shape: each one says a branch stops here.
function serialize(root) { const out = []; const walk = (node) => { if (!node) { out.push('#'); return; } out.push(String(node.val)); walk(node.left); walk(node.right); }; walk(root); return out.join(',');} function deserialize(data) { const tokens = data.split(','); let next = 0; const build = () => { const token = tokens[next++]; if (token === '#' || token === undefined) return null; const node = new TreeNode(Number(token)); node.left = build(); node.right = build(); return node; }; return build();}The trap
Writing the values with no separator, then reading one character per value, works only while every value is a single digit from 0 to 9. A value with two digits is read as two nodes, and a minus sign as a node of its own, so the rebuilt tree has the wrong shape and the wrong values.
function serialize(root) { if (!root) return '#'; return root.val + serialize(root.left) + serialize(root.right); // no separator between values} function deserialize(data) { let next = 0; const build = () => { const token = data[next++]; // reads one character per value if (token === '#' || token === undefined) return null; const node = new TreeNode(Number(token)); node.left = build(); node.right = build(); return node; }; return build();}