Serialize and Deserialize Binary Tree

Problem Statement

Serialization is the process of converting a data structure into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection.

Deserialization is the reverse process of converting the encoded data back into the original data structure.

Design an algorithm to serialize and deserialize a binary tree. You may serialize/deserialize to any string representation you want, as long as it can encode/decode the tree correctly.

Examples

Example 1

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

Tree:
      1
     / \
    2   3
       / \
      4   5

Example 2

Input: root = []
Output: []

Example 3

Input: root = [1]
Output: [1]

Intuition

We need to convert a tree into a string and back. The key challenge: preserve structure (including null nodes).

Approaches:

1. Pre-order DFS: root → left → right (with null markers)
2. Level-order BFS: level by level (with null markers)

Both work, but pre-order DFS is simpler for recursion.

Example Serialization (pre-order with 'N' for null):

      1
     / \
    2   3
       / \
      4   5

Serialize: "1,2,N,N,3,4,N,N,5,N,N"

Why this works:

• Pre-order ensures root comes before children
• Null markers preserve structure
• Can reconstruct by following same order

Pattern Recognition

This is a Tree Serialization/Design problem:

• DFS traversal with structure preservation
• String manipulation
• Symmetric encode/decode

Approach

DFS Pre-order with Null Markers

Serialize:

def serialize(root):
  result = []

  def dfs(node):
    if not node:
      result.append("N")
      return
    result.append(str(node.val))
    dfs(node.left)
    dfs(node.right)

  dfs(root)
  return ",".join(result)

Deserialize:

def deserialize(data):
  values = data.split(",")
  self.index = 0

  def dfs():
    if values[self.index] == "N":
      self.index += 1
      return None

    node = TreeNode(int(values[self.index]))
    self.index += 1
    node.left = dfs()   # Reconstruct left
    node.right = dfs()  # Reconstruct right
    return node

  return dfs()

Key Points:

• Use delimiter (comma) between values
• Mark null nodes explicitly
• Maintain index/pointer during deserialization
• Follow same traversal order

BFS Level-order (Alternative)

Use queue to serialize level by level. More intuitive but slightly more complex.

Edge Cases

• Empty tree
• Single node
• Skewed tree (all left or all right)
• Complete binary tree
• Negative values
• Large values

Complexity Analysis

Serialize

• Time: O(n) where n = number of nodes

  • Visit each node once
  • O(1) work per node

• Space: O(n)

  • Store all node values + nulls
  • Result string: O(n)

Deserialize

• Time: O(n)

  • Process each value once
  • Create n nodes

• Space: O(h) where h = height

  • Recursion stack
  • O(log n) balanced, O(n) skewed