Binary Tree Serialization and Deserialization

Tree Serialization and Deserialization

Serialization converts a binary tree into a string representation that can be stored or transmitted. Deserialization reconstructs the original tree from that string. This round-trip must be lossless — the deserialized tree must be identical to the original.

Approach 1: Pre-Order with Null Markers

The most common approach uses pre-order traversal, inserting a special marker (like "null" or "#") for null children.

SERIALIZE(node):
  if node is NULL: return "null"
  return str(node.value) + "," + SERIALIZE(node.left) + "," + SERIALIZE(node.right)

DESERIALIZE(data):
  tokens = data.split(",")
  index = 0
  function build():
    if tokens[index] == "null":
      index++; return NULL
    node = new Node(int(tokens[index]))
    index++
    node.left  = build()
    node.right = build()
    return node
  return build()

Example

Tree:           Serialized:
    1           "1,2,null,null,3,4,null,null,5,null,null"
   / \
  2   3
     / \
    4   5

Approach 2: Level-Order (BFS) Encoding

Serialize level by level, including null markers:

Tree:           Serialized:
    1           "1,2,3,null,null,4,5,null,null,null,null"
   / \
  2   3
     / \
    4   5

This is the format used by LeetCode's tree visualizer and many online judges.

Why Not Just In-Order?

In-order traversal alone cannot uniquely reconstruct a binary tree because different tree structures can produce the same in-order sequence. You need either:

• Pre-order + in-order (no null markers needed)
• Post-order + in-order
• Pre-order with null markers (single traversal)
• Level-order with null markers (single traversal)

Space Efficiency

The pre-order approach produces a string of length O(n) with 2n+1 tokens (n values + n+1 null markers). For large trees, you might use binary encoding instead of text for better compression.

Edge Cases

• Empty tree: serializes to "null"
• Single node: serializes to "1,null,null"
• Skewed tree: many consecutive null markers on one side