#140

Serialize and Deserialize Binary Tree

hard

stringtreedepth-first-searchbreadth-first-searchbinary-tree

Design a codec for a binary tree: a serialize step that turns the tree into a single string, and a deserialize step that rebuilds the exact same tree from that string. A correct codec is a perfect round trip — deserialize(serialize(t)) must equal t.

This sandbox runs one function, so implement the whole round trip in serializeDeserialize(root): serialize root to a string of your own format, then parse that string back into a tree and return it. You may choose any string format (preorder with null markers is a common one) as long as the rebuilt tree matches the original.

The tree is given (and the result is checked) as a level-order array where null marks a missing child.

Example

Input: root = [1,2,3,null,null,4,5]21435

Output: [1,2,3,null,null,4,5]21435

Serialize to a string, parse it back — the rebuilt tree is identical.

Constraints

The number of nodes in the tree is in the range [0, 10^4].
-1000 <= Node.val <= 1000

Intuition

A codec needs two halves that are perfect inverses: serialize turns a tree into a string, deserialize rebuilds the identical tree from that string. The naive instinct — serialize just the node values in order — fails, because values alone don't pin down the shape: [1, 2] could be 2 as a left child or a right child.

// Serializing values without recording the gaps loses the structure.
function serialize(root) {
  const out = [];
  const walk = (node) => { if (!node) return; out.push(node.val); walk(node.left); walk(node.right); };
  walk(root);
  return out.join(',');
}
// '1,2' — was 2 a left child or a right child? Deserialize can't know. Broken.

Brute force attempt — values only, no null markers: ambiguous, can't reconstruct the shape.

The fix is to record the nulls. The key observation: a preorder walk that emits a sentinel (say #) for every absent child captures the shape unambiguously — the sentinels mark exactly where each subtree ends, so deserialize can rebuild by consuming the tokens in the same order.

Because the sandbox runs one function, the stored solution does the whole round trip in serializeDeserialize(root): serialize to the preorder-with-sentinels string, then parse it straight back into a tree and return it. A correct codec reproduces the original exactly.

Tracing [1, 2, 3, null, null, 4, 5] — root 1, left leaf 2, right node 3 with children 4, 5:

Serialize (preorder): 1, then into 2: 2, #, # (two null children); then into 3: 3, then 4, #, #, then 5, #, #. String: 1,2,#,#,3,4,#,#,5,#,#.
Deserialize: read 1 (root), recurse left → read 2, its two #s make it a leaf; recurse right → read 3, then 4 (leaf), then 5 (leaf). The token order is the preorder, so the shape comes back exactly.

The sentinel # is what carries the structure — without a marker for each null child, the value stream is ambiguous and no deserializer can recover the original shape.
There's no lane: the mechanic is a recursive write/read of a token stream, not a scan over a fixed sequence.
This is the design→single-function reframe: LeetCode ships a two-method Codec class, but a round-trip function exercises both halves and is what the harness can run.

Optimization

Preorder with null markers

Serialize with a preorder walk: append each node's value, and a sentinel (#) for every null child. That sentinel is what makes the string unambiguous — it records the shape, so no second traversal is needed to rebuild.

Deserialize by consuming the tokens in the same preorder order: the next token is the current node (or a null if it's the sentinel), then recursively build its left subtree, then its right.

O(n) time and O(n) space for both directions (the string and the recursion).

function serializeDeserialize(root) {
  // --- serialize: preorder, '#' marks a null child ---
  const parts = [];
  const write = (node) => {
    if (!node) { parts.push('#'); return; }
    parts.push(String(node.val));
    write(node.left);
    write(node.right);
  };
  write(root);
  const data = parts.join(',');

  // --- deserialize: consume tokens in the same preorder ---
  const tokens = data.split(',');
  let i = 0;
  const read = () => {
    const token = tokens[i++];
    if (token === '#') return null;        // a null child
    const node = new TreeNode(Number(token));
    node.left = read();                    // left subtree comes next in preorder
    node.right = read();
    return node;
  };
  return read();
}

Complexity analysis

Time complexity: O(n). Here's why:

Serialize walks every node once, emitting its value or a # sentinel.
Deserialize consumes every token once.

So the round trip is O(n).

Space complexity: O(n). Here's why:

The serialized string has one token per node plus its null markers — O(n).
The recursion stack is O(h) on each side.

So O(n) overall, dominated by the string.

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
root = []null	[]null	Empty tree round-trips to empty.
root = [9]9	[9]9	Single node.
root = [8,4,9,null,null,6,10]486910	[8,4,9,null,null,6,10]486910	Interior gaps must survive the round trip exactly.
root = [-7,-8,-9]-8-7-9	[-7,-8,-9]-8-7-9	Negative values must serialize and parse back correctly.
root = [5,6,null,7,null,8]8765	[5,6,null,7,null,8]8765	A left spine: the sentinels pin down the missing right children.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor