The need for data structures also demands the ability to convert them into a storable format and reconstruct back later. Serialization is the process of converting a data structure into a sequence of bits. And deserialization is the process of reconstructing the data structure from the serialized sequence.
Introduction
Data structures play a crucial role in designing efficient software, and there are many cases where we need to share them across. Consider a binary tree to be shared, and if it’s an interprocess communication, then directly the root node of the tree can be shared. But this will not work if we have to share it across a network. Serialization will help us achieve this conversion of a data structure into a sequence, such that it can be shared across a network or stored in a memory buffer. And deserialization is used to recreate the data structure back later.
Let’s consider an example of serializing and deserializing a binary tree.
//Example of serialize and deserialize a binary tree
1
/ \ preorder serialize
2 3 ----------------------> [1, 2, 4, int_min, int_min, int_min, 3, 5, int_min, int_min, int_min]
/ / <----------------------
4 5 preorder deserialize
A naive way to do this is by maintaining any two traversals of the tree and recreating the tree back using both traversal sequences. There’s also a way to serialize the tree and restore it using a single tree traversal, either preorder or postorder, but the nulls also have to be stored here.
Now, before diving into the intuition and implementation of how to serialize and deserialize a binary tree, let’s look at it individually as how to serialize a tree and how to deserialize a tree.
Serialize a Binary Tree
Traversing the tree by following a particular order and storing the corresponding sequence will work for serializing a binary tree. The intention is not only to archive the tree nodes in a sequence but also to be able to reconstruct the tree from that sequence (to be able to serialize and deserialize a binary tree). Now, this can be achieved by following a specific traversal manner for the whole tree, such that the same manner can be used while deserializing as well.
A few of such traversals are pre-order traversal, in-order traversal, post-order traversal, etc.
Approach 1 – With Pre-order Traversal
The idea is to perform a preorder traversal of the tree and store the null values with Integer Minimum, such that a null can be identified while reconstructing the tree.
The algorithm for pre-order traversal follows as
- Initialize an empty ArrayList to store the sequence.
- Recursively traverse the tree in a pre-order manner (current, left, right).
- Add an integer minimum if the current node is null, else add the current node’s value.
Implementation
The java implementation to serialize a binary tree using pre-order traversal follows as
//java program to serialize and deserialize a binary tree
import java.util.*;
/*
contents of a tree node
*/
import java.util.*;
class Tree{
int val;
Tree left;
Tree right;
//Tree class constructor
Tree(int val){
this.val=val;
left=null;
right=null;
}
}
public class Main{
//method to serialize a binary tree using preorder traversal
public void PreorderSerialize(Tree root, ArrayList<Integer> series){
if(root == null){ //base case
series.add(Integer.MIN_VALUE);
return;
}
//push the current value
series.add(root.val);
//traverse to the left child
PreorderSerialize(root.left, series);
//traverse to the right child
PreorderSerialize(root.right, series);
}
public static void main(String[] args) {
//create a new binary tree
Tree root = new Tree(1);
root.left = new Tree(2);
root.right = new Tree(3);
root.left.left = new Tree(4);
root.right.left = new Tree(5);
Main m = new Main();
ArrayList<Integer> Preorderseries = new ArrayList<>();
m.PreorderSerialize(root, Preorderseries);
System.out.println("Preorderseries follows as");
for(int i=0;i<Preorderseries.size();i++){
System.out.print(Preorderseries.get(i)+" ");
}
}
}
Output:
Preorderseries follows as
1 2 4 -2147483648 -2147483648 -2147483648 3 5 -2147483648 -2147483648 -2147483648
C++ implementation to serialize a binary tree using pre-order traversal follows as
//C++ program to serialize and deserialize a binary tree
#include <iostream>
#include <climits>
#include <vector>
using namespace std;
struct Tree{
//contents of each tree node
int val;
Tree* left;
Tree* right;
};
//method to initialize new tree node
Tree* newNode(int val){
Tree* node = new Tree;
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
//method to serialize a binary tree using preorder traversal
vector<int> PreorderSerialize(Tree* root, vector<int> series){
if(root == NULL){ //base case
series.push_back(INT_MIN);
return series;
}
//push the current value
series.push_back(root->val);
//traverse to the left child
series = PreorderSerialize(root->left, series);
//traverse to the right child
series = PreorderSerialize(root->right, series);
return series;
}
int main() {
//create a new binary tree
Tree* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->right->left = newNode(5);
vector<int> PreorderSeries;
PreorderSeries = PreorderSerialize(root, PreorderSeries);
cout<<"Preorderseries follows as \n";
for(int i=0;i<PreorderSeries.size();i++){
cout<<PreorderSeries.at(i)<<" ";
}
}
Output:
Preorderseries follows as
1 2 4 -2147483648 -2147483648 -2147483648 3 5 -2147483648 -2147483648 -2147483648
Python implementation to serialize a binary tree using pre-order traversal follows as
#Python program to serialize and deserialize a binary tree
import sys
#contents of a tree node
class Tree:
def __init__(self, val):
self.left = None
self.right = None
self.val = val
#method to serialize the binary tree
def PreorderSerialize(root, PreorderSeries):
if(root == None): #base case
PreorderSeries.append(-sys.maxsize-1)
return
#push the current value
PreorderSeries.append(root.val)
#traverse to the left child
PreorderSerialize(root.left, PreorderSeries)
#traverse to the right child
PreorderSerialize(root.right, PreorderSeries)
#Driver code
#create a new binary tree
root = Tree(1)
root.left = Tree(2)
root.right = Tree(3)
root.left.left = Tree(4)
root.right.left = Tree(5)
PreorderSeries = []
PreorderSerialize(root, PreorderSeries)
print("Preorderseries follows as ")
for i in range(len(PreorderSeries)):
print(PreorderSeries[i], end=" ")
Output:
Preorderseries follows as
1 2 4 -9223372036854775808 -9223372036854775808 -9223372036854775808 3 5 -9223372036854775808 -9223372036854775808 -9223372036854775808
Time Complexity
This approach visits each node of the tree and appends it to the array. So time complexity will be O(N).
Space Complexity
This approach requires an array to store the serialized sequence and internally maintains a recursion stack of size H(height of binary tree). So space complexity will be O(H+N), where N is equal to the number of nodes+number of null nodes.
Approach 2 – With Post-Order Traversal
The idea is to perform post-order traversal of the tree and store the null values with Integer Minimum, such that a null can be identified while reconstructing the tree.
The algorithm for post-order traversal follows as
- Initialize an empty ArrayList to store the sequence.
- Recursively traverse the tree in a post-order manner (left, right, current).
- Add an integer minimum if the current node is null, else add the current node’s value.
Implementation
The java implementation to serialize a binary tree using post-order traversal follows as
//java program to serialize and deserialize a binary tree
import java.util.*;
/*
contents of a tree node
*/
import java.util.*;
class Tree{
int val;
Tree left;
Tree right;
//Tree class constructor
Tree(int val){
this.val=val;
left=null;
right=null;
}
}
public class Main{
//method to serialize a binary tree using postorder traversal
public void PostorderSerialize(Tree root, ArrayList<Integer> series){
if(root == null){ //base case
series.add(Integer.MIN_VALUE);
return;
}
//traverse to the left child
PostorderSerialize(root.left, series);
//traverse to the right child
PostorderSerialize(root.right, series);
//push the current value
series.add(root.val);
}
public static void main(String[] args) {
//create a new binary tree
Tree root = new Tree(1);
root.left = new Tree(2);
root.right = new Tree(3);
root.left.left = new Tree(4);
root.right.left = new Tree(5);
Main m = new Main();
ArrayList<Integer> Postorderseries = new ArrayList<>();
m.PostorderSerialize(root, Postorderseries);
System.out.println("Postorderseries follows as");
for(int i=0;i<Postorderseries.size();i++){
System.out.print(Postorderseries.get(i)+" ");
}
}
}
Output:
Postorderseries follows as
-2147483648 -2147483648 4 -2147483648 2 -2147483648 -2147483648 5 -2147483648 3 1
C++ implementation to serialize a binary tree using post-order traversal follows as
//C++ program to serialize and deserialize a binary tree
#include <iostream>
#include <climits>
#include <vector>
using namespace std;
struct Tree{
//contents of each tree node
int val;
Tree* left;
Tree* right;
};
//method to initialize new tree node
Tree* newNode(int val){
Tree* node = new Tree;
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
//method to serialize a binary tree using postorder traversal
vector<int> PostorderSerialize(Tree* root, vector<int> series){
if(root == NULL){ //base case
series.push_back(INT_MIN);
return series;
}
//traverse to the left child
series = PostorderSerialize(root->left, series);
//traverse to the right child
series = PostorderSerialize(root->right, series);
//push the current value
series.push_back(root->val);
return series;
}
int main() {
//create a new binary tree
Tree* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->right->left = newNode(5);
vector<int> PostorderSeries;
PostorderSeries = PostorderSerialize(root, PostorderSeries);
cout<<"Postorderseries follows as \n";
for(int i=0;i<PostorderSeries.size();i++){
cout<<PostorderSeries.at(i)<<" ";
}
}
Output:
Postorderseries follows as
-2147483648 -2147483648 4 -2147483648 2 -2147483648 -2147483648 5 -2147483648 3 1
Python implementation to serialize a binary tree using post-order traversal follows as
#Python program to serialize and deserialize a binary tree
import sys
#contents of a tree node
class Tree:
def __init__(self, val):
self.left = None
self.right = None
self.val = val
#method to serialize the binary tree
def PostorderSerialize(root, PostorderSeries):
if(root == None): #base case
PostorderSeries.append(-sys.maxsize-1)
return
#traverse to the left child
PostorderSerialize(root.left, PostorderSeries)
#traverse to the right child
PostorderSerialize(root.right, PostorderSeries)
#push the current value
PostorderSeries.append(root.val)
#Driver code
#create a new binary tree
root = Tree(1)
root.left = Tree(2)
root.right = Tree(3)
root.left.left = Tree(4)
root.right.left = Tree(5)
PostorderSeries = []
PostorderSerialize(root, PostorderSeries)
print("Postorderseries follows as ")
for i in range(len(PostorderSeries)):
print(PostorderSeries[i], end=" ")
Output:
Postorderseries follows as
-9223372036854775808 -9223372036854775808 4 -9223372036854775808 2 -9223372036854775808 -9223372036854775808 5 -9223372036854775808 3 1
Time Complexity
This approach visits each node of the tree and appends it to the array. So time complexity will be O(N).
Space Complexity
This approach requires an array to store the serialized sequence and internally maintains a recursion stack of size H(height of binary tree). So space complexity will be O(H+N), where N is equal to the number of nodes+number of null nodes.
Deserialize a Binary Tree
After performing the serialization, we’ll get a serialized sequence from which the original tree has to be reconstructed. As discussed earlier, we should follow the same traversal manner in which the tree has been serialized (to be able to serialize and deserialize a binary tree). Following this helps the deserialization approach in preserving the state of the original tree.
Approach 1 – With Pre-order Traversal
The idea is to traverse the given sequence and keep adding the nodes to a tree in the corresponding pre-order manner. Remember that the given sequence has to be equal to the pre-order traversal of the original tree. Else the pre-order deserialization will not recreate the original tree.
The algorithm for deserializing a pre-order traversal sequence follows as
- Traverse the sequence from the beginning.
- Create a node with the current value in the sequence.
- Recursively pass the remaining sequence to the current’s left child.
- And recursively pass the remaining sequence to the current’s right child.
- Add a null at the current node in the tree if the sequence has an integer minimum.
The java implementation to deserialize a binary tree from the pre-order traversal sequence follows as
//Java program to serialize and deserialize a binary tree
import java.util.*;
class Tree{
int val;
Tree left;
Tree right;
//Tree class constructor
Tree(int val){
this.val=val;
left=null;
right=null;
}
}
public class Main{
int index;
//method to deserialize a binary tree using preorder traversal series
public Tree PreorderDeserialize(ArrayList<Integer> series){
if(series.size() == index){ //base case
return null;
}
//adds null at relevant positions
if(series.get(index) == Integer.MIN_VALUE){
index++;
return null;
}
//add the nodes in a preorder manner current, left, right
Tree root = new Tree(series.get(index));
index++;
root.left = PreorderDeserialize(series);
root.right = PreorderDeserialize(series);
return root;
}
//function to print in order traversal of a tree
public void inOrder(Tree root){
if(root == null)
return;
inOrder(root.left);
System.out.print(root.val+" ");
inOrder(root.right);
}
public static void main(String[] args) {
int[] arr = new int[]{1, 2, 4, -2147483648, -2147483648, -2147483648, 3, 5, -2147483648, -2147483648, -2147483648};
Main m = new Main();
ArrayList<Integer> PreorderSeries = new ArrayList<Integer>();
for(int i:arr)
PreorderSeries.add(i);
m.index=0;
Tree root = m.PreorderDeserialize(PreorderSeries);
System.out.println("inorder traversal of deserialized tree follows as");
m.inOrder(root);
}
}
Output:
inorder traversal of deserialized tree follows as
4 2 1 5 3
C++ implementation to deserialize a binary tree from the pre-order traversal sequence follows as
//C++ program to serialize and deserialize a binary tree
#include <iostream>
#include <climits>
#include <vector>
using namespace std;
struct Tree{
//contents of each tree node
int val;
Tree* left;
Tree* right;
};
//method to initialize new tree node
Tree* newNode(int val){
Tree* node = new Tree;
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
int index=0;
//method to deserialize a binary tree using preorder traversal series
Tree* PreorderDeserialize(vector<int> series){
if(series.size() == index){ //base case
return NULL;
}
//adds null at relevant positions
if(series.at(index) == INT_MIN){
index++;
return NULL;
}
//add the nodes in a preorder manner current, left, right
Tree* root = newNode(series.at(index));
index++;
root->left = PreorderDeserialize(series);
root->right = PreorderDeserialize(series);
return root;
}
//function to print in order traversal of a tree
void inOrder(Tree* root){
if(root == NULL)
return;
inOrder(root->left);
cout<<root->val<<" ";
inOrder(root->right);
}
int main() {
int arr[] = {1, 2, 4, -2147483648, -2147483648, -2147483648, 3, 5, -2147483648, -2147483648, -2147483648};
vector<int> PreorderSeries;
for(int i:arr)
PreorderSeries.push_back(i);
index=0;
Tree* root = PreorderDeserialize(PreorderSeries);
cout<<"inorder traversal of deserialized tree follows as\n";
inOrder(root);
}
Output:
inorder traversal of deserialized tree follows as
4 2 1 5 3
Python implementation to deserialize a binary tree from the pre-order traversal sequence follows as
#Python program to serialize and deserialize a binary tree
import sys
#contents of a tree node
class Tree:
def __init__(self, val):
self.left = None
self.right = None
self.val = val
#method to deserialize a binary tree using preorder traversal series
def PreorderDeserialize(series):
global index
if(len(series) == index): #base case
return None
#adds null at relevant positions
if(series[index] == (-sys.maxsize-1)):
index+=1
return None
#add the nodes in preorder manner current, left, right
root = Tree(series[index])
index+=1
root.left = PreorderDeserialize(series)
root.right = PreorderDeserialize(series)
return root
#function to print inorder traversal of a tree
def inOrder(root):
if(root == None):
return
inOrder(root.left)
print(root.val,end=" ")
inOrder(root.right)
#Driver code
PreorderSeries = [1, 2, 4, -9223372036854775808, -9223372036854775808, -9223372036854775808, 3, 5, -9223372036854775808, -9223372036854775808, -9223372036854775808]
index = 0
root = PreorderDeserialize(PreorderSeries)
print("inorder traversal of deserialized tree follows as")
inOrder(root)
Output:
inorder traversal of deserialized tree follows as
4 2 1 5 3
Time Complexity
This approach traverses the whole sequence and creates a new node for the corresponding value. So the time complexity will be O(N), where N is the length of the sequence.
Space Complexity
This approach doesn’t require any auxiliary space but internally maintains a recursion stack of size O(H), where H is the height of a binary tree.
Approach 2 – With Post-order Traversal
While deserializing a post-order traversal sequence, the expected way is to build the left child, then build the right child, and then add the current node. But we cannot have access to child nodes without creating the current node. So we traverse the sequence in reverse order and follow the manner of current, right, and left.
Remember that the given sequence has to be equal to the pre-order traversal of the original tree. Else the pre-order deserialization will not recreate the original tree.
The algorithm for deserializing a post-order traversal sequence follows as
- Traverse the sequence from the end.
- Create a node with the current value in the sequence.
- Recursively pass the remaining sequence to the current’s right child.
- And recursively pass the remaining sequence to the current’s left child.
- Add a null at the current node in the tree if the sequence has an integer minimum.
Implementation
The java implementation to deserialize a binary tree from the post-order traversal sequence follows as
//Java program to serialize and deserialize a binary tree
import java.util.*;
class Tree{
int val;
Tree left;
Tree right;
//Tree class constructor
Tree(int val){
this.val=val;
left=null;
right=null;
}
}
public class Main{
int index;
//method to deserialize a binary tree using postorder traversal series
public Tree PostorderDeserialize(ArrayList<Integer> series){
if(index == -1){ //base case
return null;
}
//adds null at relevant positions
if(series.get(index) == Integer.MIN_VALUE){
index--;
return null;
}
/*
add the nodes in a postorder manner
start from the end and follow the current, right, left
which is equivalent to starting from the beginning and following left, right, and current
*/
Tree root = new Tree(series.get(index));
index--;
root.right = PostorderDeserialize(series);
root.left = PostorderDeserialize(series);
return root;
}
//function to print inorder traversal of a tree
public void inOrder(Tree root){
if(root == null)
return;
inOrder(root.left);
System.out.print(root.val+" ");
inOrder(root.right);
}
public static void main(String[] args) {
int[] arr= new int[]{-2147483648, -2147483648, 4, -2147483648, 2, -2147483648, -2147483648, 5, -2147483648, 3, 1};
Main m = new Main();
ArrayList<Integer> PostorderSeries = new ArrayList<Integer>();
for(int i:arr)
PostorderSeries.add(i);
m.index=PostorderSeries.size()-1;
Tree root = m.PostorderDeserialize(PostorderSeries);
System.out.println("inorder traversal of deserialized tree follows as");
m.inOrder(root);
}
}
Output:
inorder traversal of deserialized tree follows as
4 2 1 5 3
C++ implementation to deserialize a binary tree from the post-order traversal sequence follows as
//C++ program to serialize and deserialize a binary tree
#include <iostream>
#include <climits>
#include <vector>
using namespace std;
struct Tree{
//contents of each tree node
int val;
Tree* left;
Tree* right;
};
//method to initialize new tree node
Tree* newNode(int val){
Tree* node = new Tree;
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
int index=0;
//method to deserialize a binary tree using postorder traversal series
Tree* PostorderDeserialize(vector<int> series){
if(index == -1){ //base case
return NULL;
}
//adds null at relevant positions
if(series.at(index) == INT_MIN){
index--;
return NULL;
}
/*
add the nodes in a postorder manner
start from the end and follow the current, right, left
which is equivalent to starting from the beginning and following left, right, and current
*/
Tree* root = newNode(series.at(index));
index--;
root->right = PostorderDeserialize(series);
root->left = PostorderDeserialize(series);
return root;
}
//function to print inorder traversal of a tree
void inOrder(Tree* root){
if(root == NULL)
return;
inOrder(root->left);
cout<<root->val<<" ";
inOrder(root->right);
}
int main() {
int arr[] = {-2147483648, -2147483648, 4, -2147483648, 2, -2147483648, -2147483648, 5, -2147483648, 3, 1};
vector<int> PostorderSeries;
for(int i:arr)
PostorderSeries.push_back(i);
index = PostorderSeries.size()-1;
Tree* root = PostorderDeserialize(PostorderSeries);
cout<<"inorder traversal of deserialized tree follows as\n";
inOrder(root);
}
Output:
inorder traversal of deserialized tree follows as
4 2 1 5 3
Python implementation to deserialize a binary tree from the post-order traversal sequence follows as
#Python program to serialize and deserialize a binary tree
import sys
#contents of a tree node
class Tree:
def __init__(self, val):
self.left = None
self.right = None
self.val = val
#method to deserialize a binary tree using postorder traversal series
def PostorderDeserialize(series):
global index
if(index == -1): #base case
return None
#adds null at relevant positions
if(series[index] == -sys.maxsize-1):
index-=1
return None
'''
add the nodes in a postorder manner
start from the end and follow the current, right, left
which is equivalent to starting from the beginning and following left, right, and current
'''
root = Tree(series[index])
index-=1
root.right = PostorderDeserialize(series)
root.left = PostorderDeserialize(series)
return root
#function to print inorder traversal of a tree
def inOrder(root):
if(root == None):
return
inOrder(root.left)
print(root.val,end=" ")
inOrder(root.right)
#Driver code
PostorderSeries = [-9223372036854775808, -9223372036854775808, 4, -9223372036854775808, 2, -9223372036854775808, -9223372036854775808, 5, -9223372036854775808, 3, 1]
index=len(PostorderSeries)-1
root2 = PostorderDeserialize(PostorderSeries)
print("\ninorder traversal of deserialized tree follows as")
inOrder(root2)
Output:
inorder traversal of deserialized tree follows as
4 2 1 5 3
Time Complexity
This approach traverses the whole sequence and creates a new node for the corresponding value. So the time complexity will be O(N), where N is the length of the sequence.
Space Complexity
This approach doesn’t require any auxiliary space but internally maintains a recursion stack of size O(H), where H is the height of a binary tree.
Simpler Versions of the Problem
Now that we’ve seen how to serialize and deserialize a binary tree (general tree), there are cases where a tree can be serialized in even simpler approaches like
If the Given Tree is a Binary Search Tree
If the given tree is a binary search tree, then we can directly store the preorder or postorder traversal sequence of that tree without any need for markers to null nodes. Consider we have the preorder traversal sequence, and the algorithm for deserializing follows as
- Create a new node with the first number in the sequence(root node).
- Initialize a stack and push the root node into it.
- If the current number in the preorder sequence is less than the top node in the stack, then pop the top node from the stack.
- Create a new node with the current number as the left child of the top node. Push the new node into the stack.
- Else, keep popping the nodes from the stack until the node value is less than the current number in the preorder sequence.
- Create a new node with the current number as the right child of the last popped node. Push the new node into the stack.
- Repeat steps 3-6 by iterating the whole preorder sequence.
Is the Given Binary Tree a Complete Tree?
A binary tree is a complete tree if all the internal levels are complete, and the last level is filled in a left-to-right manner. In such a case, we can directly store the level order traversal sequence of that tree without any need for markers to null nodes.
The algorithm for deserializing follows as
- Create a new node with the first number in the sequence(root node).
- Initialize a queue and push the root node into it.
- Pop the node from the queue(current).
- Create a node with the next number in the sequence and make it the left child of the current node. Push the new node into the queue.
- Create a node with the next number in the sequence and make it the right child of the current node. Push the new node into the queue.
- Repeat steps 3-5 by iterating the whole level order sequence.
Is the Given Binary Tree a Full Tree?
A binary tree is a full tree if all the nodes in the tree have either two children or no children. In such a case, we can serialize the tree by maintaining a unique character to identify whether an internal or leaf node. It helps us exclude the need for markers to null nodes.
For example, consider the following string as preorder serialized sequence 1I2I4L5L3L, where I indicates internal nodes and L indicates leaf nodes.
**The algorithm for deserializing follows as **
- Traverse the sequence from the beginning.
- Create a node with the current value in the sequence.
- Recursively pass the remaining sequence to the current’s left child if the next character is L.
- And recursively pass the remaining sequence to the current’s right child if the next character is L.
Advantages of Serialization and Deserialization
- Serialization enables a hassle-free transmission of data structures across the network or storing them into a memory buffer.
- Not only for data structures, but serialization is also used for objects, and many ORM frameworks like hibernate use this process.
- Since serialization allows the storage of a data structure into a memory buffer, average access time can be reduced.
- Deserialization helps to trace back the state of the original form of the data structure.
- In the case of deserializing an object, it is much faster than creating a new object itself.
- Distributed systems often use this cycle of serialization and deserialization for sharing the data among the nodes.
Conclusion
Let’s have a recap on how to serialize and deserialize a binary tree,
- Serialization is the process of converting a data structure into a sequence of bits.
- Deserialization is the process of recreating the data structure back from the serialized sequence.
- Serializing a binary tree is done by storing the preorder or postorder traversal sequence of the tree by maintaining a marker to null nodes.
- Deserialization of a binary tree from the given sequence is done by recreating the tree by following the corresponding traversal manner.
- The process of serialization and deserialization has use cases in distributed systems, ORM frameworks, and file storage.
- Complete binary tree, full binary tree, and binary search tree are exceptional cases of a binary tree that doesn’t need to maintain a marker for the null nodes.
