L36. Serialize and De-serialize Binary Tree | C++ | Java

Overview

Serialization and deserialization are foundational operations in computer science used to convert an in-memory data structure (like a binary tree) into a persistent or transmittable format (like a string) and subsequently reconstruct the exact tree from that string. This chapter breaks down how to design a robust Level-Order (BFS) serialization and deserialization engine, complete with C++ and Java implementations, explicit queue handling, delimiter management, and edge-case mitigation.

1. Why Do We Need Serialization and Deserialization?

When working with data structures like binary trees, objects exist purely in volatile RAM. If you need to transmit a tree over a network, save it to a file, or store it in a database, the hierarchical pointer-based layout must be flattened into a linear format (such as a string or byte stream).

• Serialization: Transforming a binary tree root into a serialized string representation.
• Deserialization: Taking that exact serialized string and rebuilding the original binary tree with all its structural properties intact.

2. Core Mental Model: Level-Order Traversal

While serialization can theoretically be achieved using Pre-Order, Post-Order, or In-Order traversals, Level-Order (Breadth-First Search / BFS) traversal is the most intuitive approach because it visits nodes level by level, top-to-bottom, left-to-right.

Real-Life Analogy: The Flattened Family Tree

Imagine explaining a family tree over the telephone. Instead of jumping up and down branches, you systematically name every person generation by generation, starting from the root parent. If a person does not have a child on the left or right, you explicitly state "null" (or a special marker like # or n) so that whoever is drawing the tree on the other end knows exactly where the empty spaces belong. Without those placeholders, you wouldn't know whether a child belongs to the left or right branch when reconstructing the tree.

3. The Serialization Workflow (String Generation)

To serialize a tree using Level-Order traversal:

1. Initialize a queue and push the root node into it.
2. While the queue is not empty, pop the front node.
3. If the node is null: Append a special marker (e.g., # or n) followed by a separator (like a comma or space) to your string accumulator. Do not attempt to push its children to the queue.
4. If the node is valid: Append its value to the string, followed by a separator. Push both its left and right children into the queue (even if they are null, so their absence is captured).

Example Tree Structure

        1
       / \
      2   13
         /  \
        4    5

Generated Level-Order String: 1,2,13,#,#,4,5,#,#,#,#

4. The Deserialization Workflow (Reconstruction)

Deserialization performs the exact inverse operation. You parse the string, extract tokens sequentially, and attach them back to nodes popped from a queue.

Step-by-Step Deserialization Logic:

1. Handle edge cases: If the string is empty or null, return null.
2. Split the string into tokens using your chosen delimiter (comma or space).
3. Create the root node using the first token and push it into a queue.
4. Maintain an index pointer (or iterator) to track subsequent tokens in the array.
5. While the queue is not empty:
   • Pop the current parent node.
   • Process Left Child: Read the next token from the string array. If it is not a null marker (# or n), create a new left child node, link it to parent.left, and push the new child into the queue. If it is a null marker, leave parent.left as null.
   • Process Right Child: Read the subsequent token. If it is not a null marker, create a new right child node, link it to parent.right, and push it into the queue.

5. C++ Implementation

Below is the complete C++ solution utilizing std::stringstream and std::getline for parsing comma-delimited strings.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (!root) return "";
        
        string s = "";
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            
            if (node == nullptr) {
                s.append("#,");
            } else {
                s.append(to_string(node->val) + ",");
                q.push(node->left);
                q.push(node->right);
            }
        }
        return s;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.size() == 0) return nullptr;
        
        stringstream s(data);
        string str;
        getline(s, str, ',');
        
        TreeNode* root = new TreeNode(stoi(str));
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            TreeNode* parent = q.front();
            q.pop();
            
            // Read Left Child
            string leftStr;
            getline(s, leftStr, ',');
            if (leftStr == "#") {
                parent->left = nullptr;
            } else {
                TreeNode* leftNode = new TreeNode(stoi(leftStr));
                parent->left = leftNode;
                q.push(leftNode);
            }
            
            // Read Right Child
            string rightStr;
            getline(s, rightStr, ',');
            if (rightStr == "#") {
                parent->right = nullptr;
            } else {
                TreeNode* rightNode = new TreeNode(stoi(rightStr));
                parent->right = rightNode;
                q.push(rightNode);
            }
        }
        return root;
    }
};

6. Java Implementation

Below is the complete Java solution utilizing StringBuilder for efficient string concatenation and .split() for tokenizing space- or comma-delimited data.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "";
        
        StringBuilder res = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            
            if (node == null) {
                res.append("n ");
                continue;
            }
            res.append(node.val + " ");
            q.add(node.left);
            q.add(node.right);
        }
        return res.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> q = new LinkedList<>();
        q.add(root);
        
        int i = 1;
        while (!q.isEmpty() && i < values.length) {
            TreeNode parent = q.poll();
            
            // Process Left Child
            if (!values[i].equals("n")) {
                TreeNode leftNode = new TreeNode(Integer.parseInt(values[i]));
                parent.left = leftNode;
                q.add(leftNode);
            }
            i++;
            
            // Process Right Child
            if (i < values.length && !values[i].equals("n")) {
                TreeNode rightNode = new TreeNode(Integer.parseInt(values[i]));
                parent.right = rightNode;
                q.add(rightNode);
            }
            i++;
        }
        return root;
    }
}

7. Complexity Analysis

8. Summary and Key Takeaways

• Problem Purpose: Serialization bridges the gap between volatile memory pointers and persistent or transmittable linear formats (strings/streams).
• Traversal Strategy: Level-Order (BFS) traversal combined with explicit null markers (# or n) guarantees unambiguous reconstruction of tree topologies.
• Queue Mechanics: During serialization, null children are explicitly pushed as markers; during deserialization, non-null tokens instantiate new nodes and push them back into the queue for child linkage.
• Language-Specific Parsing:
  • C++ leverages std::stringstream and std::getline with custom delimiters.
  • Java leverages StringBuilder for fast concatenation and .split() arrays for token traversal.
• Time & Space Efficiency: Both serialization and deserialization run in optimal $O(N)$ time and utilize $O(N)$ auxiliary space for queues and string storage.