Serialize and Deserialize Binary Tree

Description

Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

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

Example 2:
Input: root = []
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 104].
• -1000 <= Node.val <= 1000

Primary Approach: Preorder DFS with Sentinel Values ($O(N)$ Time, $O(N)$ Space)

Intuition

Standard Preorder traversal ($\text{Root}\to \text{Left}\to \text{Right}$) alone cannot uniquely identify a binary tree because structure is lost. However, if we explicitly include null markers (sentinels) in the traversal, the tree structure becomes 100% deterministic and easy to reconstruct:

1. Serialization: Perform Preorder DFS. For a non-null node, append its value followed by a delimiter (,). For null nodes, append a sentinel character like "N,".
2. Deserialization: Split the string by delimiter into a global Queue. Because Preorder processes $\text{Root}\to \text{Left}\to \text{Right}$, popping the queue sequentially provides the exact order needed to recursively build the root, left subtree, and right subtree.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
 
public class Codec {
    private static final String NULL_MARKER = "N";
    private static final String DELIMITER = ",";
 
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        buildString(root, sb);
        return sb.toString();
    }
 
    private void buildString(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append(NULL_MARKER).append(DELIMITER);
            return;
        }
 
        // Preorder DFS: Root -> Left -> Right
        sb.append(node.val).append(DELIMITER);
        buildString(node.left, sb);
        buildString(node.right, sb);
    }
 
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
       // Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(DELIMITER))); old
        Queue<String> nodes = new ArrayDeque<>(Arrays.asList(data.split(DELIMITER)));
        return buildTree(nodes);
    }
 
    private TreeNode buildTree(Queue<String> nodes) {
        String val = nodes.poll();
 
        if (val == null || val.equals(NULL_MARKER)) {
            return null;
        }
 
        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = buildTree(nodes);
        node.right = buildTree(nodes);
 
        return node;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Every node (and null leaf pointer) is visited once during both encoding and decoding.
• Space Complexity: $O(N)$ — The output string stores $2N+1$ elements (nodes + null markers). The recursion call stack and Queue take $O(N)$ space in the worst case.

---

Alternative Approach: Level-Order BFS ($O(N)$ Time, $O(N)$ Space)

Intuition

This mirrors how LeetCode formats binary tree test cases internally using Breadth-First Search:

1. Serialize: Process nodes level by level using a Queue. Append node.val or "N" to a StringBuilder, pushing node.left and node.right into the queue regardless of whether they are null.
2. Deserialize: Read the array of values starting with root = values[0]. Use a Queue to attach left child values[i] and right child values[i+1] to each parent popped from the queue.

import java.util.LinkedList;
import java.util.Queue;
 
public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "";
 
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
 
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
 
            if (node == null) {
                sb.append("N,");
                continue;
            }
 
            sb.append(node.val).append(",");
            queue.add(node.left);
            queue.add(node.right);
        }
 
        return sb.toString();
    }
 
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.isEmpty()) return null;
 
        String[] values = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
 
        for (int i = 1; i < values.length; i++) {
            TreeNode parent = queue.poll();
 
            // Process Left Child
            if (!values[i].equals("N")) {
                TreeNode left = new TreeNode(Integer.parseInt(values[i]));
                parent.left = left;
                queue.add(left);
            }
 
            // Process Right Child
            i++;
            if (!values[i].equals("N")) {
                TreeNode right = new TreeNode(Integer.parseInt(values[i]));
                parent.right = right;
                queue.add(right);
            }
        }
 
        return root;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Processes every node and null marker in level-order sequence.
• Space Complexity: $O(N)$ — BFS queue holds up to $O(W)$ nodes ($W\le N/2$ at the bottom level) plus the string representation of $N$ nodes.

---

Key Interview Discussion Points

• Use StringBuilder over String Concatenation: Always use StringBuilder in Java. Repeated string concatenation (s += val) takes $O(N^2)$ time due to string immutability, while StringBuilder.append() operates in $O(1)$ time.
• Why Preorder DFS is Preferred: While BFS is intuitive, Preorder DFS requires significantly cleaner code (~25 lines vs ~45 lines) with fewer boundary checks during deserialization.
• BST Optimization Follow-Up (LeetCode 449): If told the input tree is a Binary Search Tree, emphasize that null markers are unnecessary! A standard preorder traversal can be reconstructed into a BST in $O(N)$ time using standard dynamic range bounds (min, max).

---

Easy Memory Rule

“Preorder DFS ($\text{Root}\to \text{Left}\to \text{Right}$) + Null Markers (N) $\to$ Store in Queue $\to$ Reconstruct recursively!”