Introduction

In this guide, we will write a C++ program to serialize and deserialize a binary tree.
Serialization is the process of converting a data structure into a format that can be easily stored and reconstructed later.
Deserialization is the reverse process of converting the serialized format back into the original data structure.

Program Structure

The program will follow these steps:

1. Define a TreeNode structure to represent nodes in the binary tree.
2. Write a recursive serialize function that converts the binary tree to a string.
3. Write a recursive deserialize function that reconstructs the tree from the serialized string.

Code Implementation

// C++ program to serialize and deserialize a binary tree

#include <iostream>
#include <sstream>
#include <string>
using namespace std;

// Define the structure of a tree node
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    // Constructor to initialize the tree node
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// Helper function to serialize the binary tree into a string
void serialize(TreeNode* root, ostringstream& out) {
    if (root == NULL) {
        out << "# ";  // Use "#" to represent null nodes
        return;
    }

    // Serialize the current node's value
    out << root->val << " ";

    // Recursively serialize the left and right subtrees
    serialize(root->left, out);
    serialize(root->right, out);
}

// Function to serialize the tree (called by the main function)
string serialize(TreeNode* root) {
    ostringstream out;
    serialize(root, out);
    return out.str();
}

// Helper function to deserialize the string into a binary tree
TreeNode* deserialize(istringstream& in) {
    string val;
    in >> val;

    // If we encounter "#", it represents a null node
    if (val == "#")
        return NULL;

    // Create a new node with the current value
    TreeNode* node = new TreeNode(stoi(val));

    // Recursively deserialize the left and right subtrees
    node->left = deserialize(in);
    node->right = deserialize(in);

    return node;
}

// Function to deserialize the string (called by the main function)
TreeNode* deserialize(const string& data) {
    istringstream in(data);
    return deserialize(in);
}

// Helper function to perform in-order traversal of the binary tree (for testing purposes)
void inOrderTraversal(TreeNode* root) {
    if (!root) return;

    inOrderTraversal(root->left);
    cout << root->val << " ";
    inOrderTraversal(root->right);
}

int main() {
    /* Sample Binary Tree:
              1
            /   \
           2     3
                / \
               4   5
    */

    // Creating the binary tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->right->left = new TreeNode(4);
    root->right->right = new TreeNode(5);

    // Serialize the tree
    string serializedData = serialize(root);
    cout << "Serialized Tree: " << serializedData << endl;

    // Deserialize the serialized string back to a binary tree
    TreeNode* deserializedTree = deserialize(serializedData);

    // Perform in-order traversal to verify the deserialized tree
    cout << "In-order Traversal of Deserialized Tree: ";
    inOrderTraversal(deserializedTree);
    cout << endl;

    return 0;
}

Explanation

Let’s break down the program:

1. TreeNode structure: This structure represents a node in the binary tree. Each node stores a value val and pointers to its left and right children.
2. serialize function: This function serializes the binary tree into a string. It uses pre-order traversal (root, left, right) and adds a special character (in this case, #) to represent null nodes. The serialized string stores the tree’s structure in a way that allows it to be reconstructed later.
3. deserialize function: This function deserializes the string back into the binary tree. It reads the string and creates nodes for non-null values, recursively reconstructing the left and right subtrees for each node.
4. inOrderTraversal function: This helper function performs an in-order traversal (left subtree, root, right subtree) of the tree to display the tree’s structure after deserialization. It is used for verification.

How the Algorithm Works

The serialize function performs a pre-order traversal of the tree, converting the nodes into a space-separated string. For each node, it records the value followed by a space, and for null nodes, it adds the # symbol to represent the absence of a child. This allows the tree’s structure to be preserved.

The deserialize function reads the serialized string and constructs the binary tree by recursively creating nodes for valid values and assigning null for #. The function reads the values in pre-order fashion, ensuring that the tree is rebuilt in the same structure.

Sample Output

If you run the above program with the provided sample binary tree, the output will be:

Serialized Tree: 1 2 # # 3 4 # # 5 # # 
In-order Traversal of Deserialized Tree: 2 1 4 3 5 

The in-order traversal confirms that the deserialized tree has the same structure as the original tree.

Conclusion

In this program, we implemented the serialize and deserialize operations for a binary tree in C++. Serialization converts the tree into a string representation that can be stored or transmitted, while deserialization reconstructs the original tree from the string. This approach is useful for saving or transmitting tree structures in applications like databases, file storage, and network communication.

The time complexity of both serialization and deserialization is O(N), where N is the number of nodes in the tree. Each node is visited exactly once during the process, making the algorithm efficient for large trees.