Back to ChallengesSerialize and Deserialize Binary TreeHard 45 min

Serialize and Deserialize Binary Tree

Design an algorithm to **serialize** a binary tree to a string and **deserialize** that string back to the original tree structure.

- `serialize(root)` → string

- `deserialize(data)` → TreeNode

There is no restriction on how your serialization/deserialization algorithm works, as long as a tree can be serialized to a string and this string can be deserialized to the original tree structure.

Examples

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

Output: Same tree reconstructed

serialize then deserialize returns the same tree.

Input: root = []

Output: null

Empty tree.

Constraints

• Number of nodes in [0, 10^4]
• -1000 <= Node.val <= 1000

Complexity Analysis

Time

O(n) for both serialize and deserialize.

Space

O(n) for the output string and reconstruction queue.

Test Cases

#1 Standard tree round-trip

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

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

#2 Empty tree

Input: []

Expected: []

#3 Single node

Input: [1]

Expected: [1]

#4 Left-skewed

Input: [1,2,null,3]

Expected: [1,2,null,3]

JavaScript

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val; this.left = left; this.right = right;
  }
}
function buildTree(arr) {
  if (!arr || arr.length === 0) return null;
  const root = new TreeNode(arr[0]);
  const q = [root]; let i = 1;
  while (q.length && i < arr.length) {
    const n = q.shift();
    if (arr[i] != null) { n.left = new TreeNode(arr[i]); q.push(n.left); } i++;
    if (i < arr.length && arr[i] != null) { n.right = new TreeNode(arr[i]); q.push(n.right); } i++;
  }
  return root;
}
function treeToArray(root) {
  if (!root) return [];
  const res = [], q = [root];
  while (q.length) {
    const n = q.shift();
    res.push(n ? n.val : null);
    if (n) { q.push(n.left); q.push(n.right); }
  }
  while (res[res.length - 1] === null) res.pop();
  return res;
}

/**
 * Encodes a tree to a single string.
 * @param {TreeNode} root
 * @return {string}
 */
function serialize(root) {
  // Your code here
}

/**
 * Decodes your encoded data to tree.
 * @param {string} data
 * @return {TreeNode}
 */
function deserialize(data) {
  // Your code here
}

// Test: serialize then deserialize should yield same tree
const root = buildTree([1,2,3,null,null,4,5]);
const serialized = serialize(root);
console.log("Serialized:", serialized);
const deserialized = deserialize(serialized);
console.log("Deserialized:", JSON.stringify(treeToArray(deserialized)));
// Expected: [1,2,3,null,null,4,5]

Output

Click "Run Code" to see output here...