Construction & Serialization

Serialize / Deserialize

Convert a tree to a string and back. Use pre-order traversal, recording 'null' for missing children. To deserialize, read values in order: first value is the root, then recursively build left and right subtrees.

O(n)

How It Works

Serialization turns a tree into a string; deserialization inverts it exactly. The standard scheme is a pre-order walk that writes each node's value and an explicit marker (like "#") for every null child. Those null markers are the crucial ingredient: they pin down each node's exact shape, so a single traversal order suffices — no second traversal needed, unlike the pre+in reconstruction, and duplicates cause no ambiguity.

Deserialization consumes tokens in the same order the walk produced them: read a token, if it is the null marker return null, otherwise create the node and recursively build its left then right subtree. The token stream and the recursion stay in lockstep, so no searching is required. Both directions touch each node once — O(n) time, O(n) output, O(h) recursion space. BFS-based encoding is an equally valid alternative that many languages' library formats resemble.

Step-by-Step Visualization

Serialize tree to string with null markers

Output1,2,N,N,3,4,N,N,5,N,N

1/3

Code

Java

static String serialize(TreeNode root) {
  if (root == null) return "null";
  return root.val + "," + serialize(root.left) + "," + serialize(root.right);
}

static TreeNode deserialize(String data) {
  Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(",")));
  return buildTree(queue);
}

static TreeNode buildTree(Queue<String> queue) {
  String val = queue.poll();
  if ("null".equals(val)) return null;
  TreeNode node = new TreeNode(Integer.parseInt(val));
  node.left = buildTree(queue);
  node.right = buildTree(queue);
  return node;
}

Tips & Gotchas

1Use pre-order traversal with null markers

2Serialize: record value or 'null' for each node

3Deserialize: read values in order, recursively build tree

Practice Problems

1Serialize and Deserialize Binary Tree
2Serialize and Deserialize BST
3Find Duplicate Subtrees
4Subtree of Another Tree

About the Construction & Serialization Pattern

Build a tree from its traversal orders, or convert a tree to/from a string representation. These test your understanding of how traversal orders uniquely define a tree's structure.

Key insight

Tree problems are almost always DFS (recursion) or BFS (level-order). The pattern: solve for children, combine results, return up. BST's sorted property lets you prune half the tree.

Common Trees Interview Problems

Maximum Depth of Binary Tree
Validate BST
Binary Tree Level Order Traversal
Lowest Common Ancestor
Serialize and Deserialize Binary Tree
Diameter of Binary Tree

Frequently Asked Questions

Why do null markers remove the need for a second traversal order?

Reconstruction from a single order is ambiguous only because you cannot tell where subtrees end. Explicit nulls mark every boundary, so the pre-order stream deterministically encodes the full shape. Two traversal orders are the alternative fix when nulls are not recorded.

Can I serialize a BST more compactly than a general binary tree?

Yes. A BST's pre-order sequence alone reconstructs the tree without null markers: value ranges inherited from ancestors determine where each subtree ends. That halves the output size, but it only works because the BST ordering substitutes for the structural markers.

DFS or BFS encoding — does it matter?

Both are O(n) and both round-trip correctly with null markers, so choose whichever deserializer you find easier to write. Pre-order DFS pairs naturally with recursion; BFS pairs with a queue and can be friendlier for very deep trees since it avoids deep recursion.