Serialize & Deserialize Binary Tree

Problem Statement

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

Example:

Input:    1
         / \
        2   3
           / \
          4   5

Serialized: "1,2,NULL,NULL,3,4,NULL,NULL,5,NULL,NULL"
Deserialize(serialized) → original tree

Approach 1: Preorder Traversal with NULL markers

Explanation: Serialize tree recursively using preorder traversal, marking NULLs for missing children. Deserialize using same traversal.

Time Complexity: O(n)

Space Complexity: O(n)

function serialize(root):
    if root == NULL: return "NULL,"
    return str(root.val)+"," + serialize(root.left) + serialize(root.right)

function deserialize(data):
    list = data.split(",")
    return helper(list)

function helper(list):
    val = list.pop(0)
    if val == "NULL": return NULL
    node = TreeNode(val)
    node.left = helper(list)
    node.right = helper(list)
    return node

Approach 2: Level Order (BFS) Traversal

Explanation: Use a queue for BFS. Serialize level by level including NULLs. Deserialize using the queue to reconstruct tree level by level.

Time Complexity: O(n)

Space Complexity: O(n)

function serialize(root):
    if root == NULL: return ""
    queue = [root]
    result = []
    while queue:
        node = queue.pop(0)
        if node:
            result.append(str(node.val))
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append("NULL")
    return ",".join(result)

function deserialize(data):
    if data == "": return NULL
    vals = data.split(",")
    root = TreeNode(vals[0])
    queue = [root]
    i = 1
    while queue:
        node = queue.pop(0)
        if vals[i] != "NULL":
            node.left = TreeNode(vals[i])
            queue.append(node.left)
        i += 1
        if vals[i] != "NULL":
            node.right = TreeNode(vals[i])
            queue.append(node.right)
        i += 1
    return root

Approach 3: DFS with Stack (Iterative Serialization)

Explanation: Use a stack for iterative preorder traversal. Push NULL markers for missing children. Deserialize using list iteration.

Time Complexity: O(n)

Space Complexity: O(n)

function serialize(root):
    stack = [root]
    result = []
    while stack:
        node = stack.pop()
        if node:
            result.append(str(node.val))
            stack.push(node.right)
            stack.push(node.left)
        else:
            result.append("NULL")
    return ",".join(result)

function deserialize(data):
    list = data.split(",")
    index = 0
    function helper():
        nonlocal index
        if list[index] == "NULL":
            index += 1
            return NULL
        node = TreeNode(list[index])
        index += 1
        node.left = helper()
        node.right = helper()
        return node
    return helper()