Serialize and Deserialize Binary Trees
In order to save a tree in a file that can later be restored, serialisation is used. The tree's structure must be preserved. Deserialization involves reading a tree from a file again.
When a binary search tree is provided, we can save it by either storing preorder traversal or postorder traversal. Only preorder or postorder traversal is necessary and sufficient in the case of Binary Search Trees to store structure data.
If the given binary tree is a Complete Binary Tree, the following must be done. All the levels of a binary tree must be fully filled, with the exception of the last level, and all of the last level's nodes must be as far to the left as feasible (Binary Heaps are complete Binary Tree). Level order traversal is sufficient to store a whole binary tree. The first node is the root, the following two are nodes of the following level, the following four are nodes of the following level, and so on.
If the given binary tree is a Full Binary Tree, the following must be done. A full binary tree is one that has either 0 or 2 children at each node. Since every internal node has two offspring, such trees are simple to serialise. Preorder traversal can be easily stored, and we can also include a bit with each node to specify whether it is an internal node or a leaf node.
Storing a general Binary Tree:
Storing both Inorder and Preorder traversals is an easy fix. The space needed for this solution is twice as large as for Binary Tree. Preorder traversal and a marker for NULL pointers can be stored in less space.
An assumption is to be made which is indicating a NULL pointer with -1.
Consider the following examples
Input:
Output: 123 146 -1 -1 -1
So, in the above example, the elements are stored accordingly in the Depth First Search manner.
Input:
Output: 30 18 -1 -1 32 -1 -1
Input:
Output: 30 18 3 -1 -1 12 11 -1 15 -1 -1 -1 32 -1 -1
Input:
Output: 30 -1 32 -1 4 -1 8 -1 -1
These are few examples of how the elements of the binary tree are stored in the file during the serialization process.
// An example Java programme for serialising and deserializing Binary Trees.
import java.util.*;
/*
A TreeNode is created which has a value, pointer to the left child and a pointer to the right child.
*/
class BTreeNode {
int data;
BTreeNode left;
BTreeNode right;
BTreeNode(int x)
{
data = x;
}
} // BTreeNode
// A class for the binary tree is created.
class BinaryTreeDemo {
BTreeNode root;
// A Tree is given to a single string.
public static String serialize (BTreeNode root)
{
//Checking if the given tree is empty or not.
if (root == null) {
return null;
}
//A stack of datatype BTreeNode is created.
Stack<BTreeNode> st = new Stack<>();
st.push(root); //Root element is added to the stack.
// An arraylist which can take string parameters is created.
List<String> list = new ArrayList<>();
while (!s.isEmpty()) {
BTreeNode t = st. pop ();
// A marker is stored, if the current node is NULL.
if (t == null) {
list.add("#");
}
else {
/*
If the current node is not NULL, then store the current node and recur for its children.
*/
list.add ("" + t.data);
st. push(t.right);
st. push(t.left);
}
}
return String.join (",", l);
}
static int temp;
// This part of code decodes the data which is encoded.
public static BTreeNode deserialize (String val)
{
if (val == null)
return null;
temp = 0;
String [] array = val.split (",");
return helper(array);
}
public static BTreeNode helper (String [] array)
{
if (array [temp]. equals ("#"))
return null;
// A node is created having its item and can recur for its children.
BTreeNode root
= new BTreeNode (Integer.parseInt (array[temp]));
temp++;
root.left = helper(array);
temp++;
root.right = helper(array);
return root;
}
// A Inorder traversal to test the constructed tree.
static void Inorder (BTreeNode root)
{
if (root != null) {
Inorder (root.left);
System.out.print(root.data + " ");
Inorder(root.right);
}
}
/*
Driver code for the above Methods.
*/
public static void main (String args[])
{
// Now let’s construct a binary tree.
BinaryTreeDemo btree = new BinaryTreeDemo();
btree.root = new BTreeNode(30);
btree.root.left = new BTreeNode(18);
btree.root.right = new BTreeNode(32);
btree.root.left.left = new BTreeNode(14);
btree.root.left.right = new BTreeNode(22);
btree.root.left.right.left = new BTreeNode(20);
btree.root.left.right.right = new BTreeNode(24);
String serialize = serialize (btree.root);
System.out.println ("The view of the tree after serialization:");
System.out.println(serialize);
System.out.println();
// Now let’s perform deserialization.
BTreeNode tp = deserialize (serialize);
System.out.println(
"The Inorder Traversal of the binary tree which is constructed from serialized String is:");
Inorder(tp);
} // main
} // BinaryTreeDemo
If there are n keys, then the preceding technique needs n+1 markers, which may be preferable to the straightforward solution (storing keys twice) in cases where keys are large or have substantial data items attached to them.
Optimization:
There are numerous approaches to optimise the previous solution. A deeper inspection of the serialised trees shown above reveals that every leaf node needs two markers. To store a distinct bit with each node to indicate whether it is internal or external is a straightforward optimization. In this method, since leaves can be distinguished by an extra bit, we don't need to store two markers with each leaf node. Marker for internal nodes with a single child is still required.