Serialize and Deserialize a Binary Tree

Serializing a tree means converting it to a flat string (or array) that can be stored, sent over a network, or passed to another process. Deserializing rebuilds the exact original tree from that encoding. This is LeetCode 297 and appears in system-design and coding interviews alike.

Why Preorder With Null Sentinels

Inorder traversal alone cannot uniquely identify a tree — many different trees produce the same inorder sequence. Preorder fixes this because it always records the root before the subtree children, and explicit null markers ("N" below) preserve the exact shape.

Serialize

class TreeNode {
  constructor(val = 0, left = null, right = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

function serialize(root) {
  const parts = [];

  function dfs(node) {
    if (!node) { parts.push("N"); return; }
    parts.push(String(node.val));
    dfs(node.left);
    dfs(node.right);
  }

  dfs(root);
  return parts.join(",");
}

// Tree:    1
//         / \
//        2   3
//           / \
//          4   5
//
// serialize(root) => "1,2,N,N,3,4,N,N,5,N,N"

Every node emits exactly three tokens: its value, then whatever its left subtree emits, then whatever its right subtree emits. Null nodes emit a single "N". This encoding is self-delimiting — no length headers needed.

Deserialize

Reconstruction works by reading tokens left to right in the same preorder sequence. A queue (or pointer into the array) serves as a cursor:

function deserialize(data) {
  const tokens = data.split(",");
  let index = 0;

  function dfs() {
    if (tokens[index] === "N") { index++; return null; }
    const node = new TreeNode(Number(tokens[index++]));
    node.left  = dfs();   // consume left subtree tokens
    node.right = dfs();   // consume right subtree tokens
    return node;
  }

  return dfs();
}

// Round-trip check:
const root = new TreeNode(1,
  new TreeNode(2),
  new TreeNode(3, new TreeNode(4), new TreeNode(5)),
);
const encoded = serialize(root);          // "1,2,N,N,3,4,N,N,5,N,N"
const rebuilt = deserialize(encoded);
console.log(serialize(rebuilt) === encoded); // true

The index variable advances monotonically — each call to dfs consumes exactly the tokens belonging to one subtree, so the recursion naturally partitions the token array.

Complexity

n tokens are written and read exactly once each. Stack depth equals tree height.

Alternative Encodings

BFS (level-order) serialization is what LeetCode uses in its tree visualizer: [1,2,3,null,null,4,5]. It is slightly more compact for wide trees but the deserializer requires a queue and index-arithmetic. Preorder is simpler to implement from scratch and sufficient for any interview setting.

Up Next

All the tree operations so far degrade to O(n) on an unbalanced tree. AVL trees enforce a height balance factor to keep every operation at O(log n).