Serialize and Deserialize Binary Tree

We have given a binary tree containing N number of nodes where each node has some value. We need to serialize and deserialize the binary tree.

Serialize

The process of storing a tree in a file without disturbing its structure is called serialization.

DeserializeSerialize and Deserialize Binary Tree

The process of retrieval of a tree or reading the tree in the same order from the file is called deserialization.

Example

Inorder Traversal of binary tree

Input: 7

             \

               14

                 \

                   21

Output : 7 14 21

Input :        7

                /

             14

             /

          21

Output : 7 14 21

Input : 14

           /    \

         7       21

Output :7 14 21

Inorder Traversal Method

Algorithm

1. Initialize a structure node that will help in forming a tree containing a variable next and two pointers left and right.
2. Create a function newNode of return type node that’ll accept a value and form a node for it while initializing left and right children of that node as null. Return a new node.
3. Create another function serialize to store the tree in a file that accepts the pointer to the root node and a file pointer as a parameter.
4. If the root node is null, write -1 in the file and return.
5. Else store the current node in the file and make recursive calls for the left and write nodes.
6. Create another function deserialize to retrieve the tree back from the file that accepts a pointer to the root node and a file pointer as a parameter.
7. Start reading the file. If there is no value in a file or the value stored is -1, return.
8. Else create a node for the current value and make recursive calls for its children i.i. left and right nodes.
9. Create another function inorder that accepts a pointer to the root node and prints the tree by making recursive calls for the left and right nodes.
10. In the main function form the tree using node structure.
11. Open the file to serialize the tree. If the file not found print the error message.
12. Else close the file after writing.
13. Deserialize the file and call the inorder function to get the inorder traversal of the tree.

C++ Program for Serialize and Deserialize Binary Tree

#include <bits/stdc++.h>
using namespace std; 
  
struct node{ 
    int next; 
    struct node* left, *right; 
}; 
  
node* newNode(int next){ 
    node* temp = new node; 
    temp->next = next; 
    temp->left = temp->right = NULL; 
    return (temp); 
} 
  
// This function stores a tree in a file
void serialize(node *root, FILE *f){
    if(root == NULL){ 
        fprintf(f, "%d ", -1); 
        return; 
    } 
  
    // Else, store current node and call function for it's children
    fprintf(f, "%d ", root->next); 
    serialize(root->left, f); 
    serialize(root->right, f); 
} 
  
// This function constructs a tree from a file
void deserialize(node *&root, FILE *f){ 
    // Read next item from file. If theere are no more items
    // item is -1, then return 
    int val; 
    if(!fscanf(f, "%d ", &val) || val == -1)
       return; 
  
    // Else create node with this item and call function for it's children 
    root = newNode(val); 
    deserialize(root->left, f); 
    deserialize(root->right, f); 
} 
  
// A simple inorder traversal used for testing the constructed tree 
void inorder(node *root){ 
    if(root){ 
        inorder(root->left); 
        cout<<root->next<<" "; 
        inorder(root->right); 
    } 
}
int main(){ 
    struct node *root        = newNode(14); 
    root->left               = newNode(7); 
    root->right              = newNode(21); 
  
    //serialize the tree into the file 
    FILE *f = fopen("tree.txt", "w"); 
    if(f == NULL){ 
        cout<<"Could not open file"; 
        return 0; 
    } 
    serialize(root, f); 
    fclose(f); 
  
    // deserialize the storeed tree
    node *root1 = NULL; 
    f = fopen("tree.txt", "r"); 
    deserialize(root1, f); 
    inorder(root1); 
  
    return 0; 
}

7 14 21

Complexity Analysis for Serialize and Deserialize Binary Tree

Time Complexity: O(n) where n is the number of nodes present in the given tree.

Space Complexity: O(n) because we stored the inorder traversal of the given tree for a deserializing binary tree.

References