Serialize and Deserialize a Binary Tree

Serialize and Deserialize a Binary Tree

---

Design an algorithm to serialize and deserialize given Binary Tree.  Serialization is to store tree in a File/String, so that it can be later restored. 
Deserialization is reading tree back from file.

Lets understand the problem statement graphically and it will be more clear,

We need to Serialize given Binary Tree into String(So that we can write it to File or transfer it). 

Also, we need to read the Serialized String and Deserialize it back to original Binary Tree.

Algorithm

---

Serialization:

For Serialization process, we can read the given Binary Tree in any order and create a String representation of tree as long as same String is capable of converting back to same given Binary Tree.

Pre order Traversal will help us in Serialization process.
In Pre order traversal we first read the Node data, then visit Left Subtree and then Right Subtree.
For more details on Tree Traversal: Binary Tree Traversals - Inorder, Preorder, Postorder, Levelorder

We will read the tree in Pre order traversal and store the node data in a string separated by comma.
Whenever we will encounter null node we will store "null" string against it as a indication that it is end of Tree.

Lets see how Pre order traversal of Binary Tree looks like,


Deserialization:

Deserialization process is to convert Serialized string back to original Binary Tree
We use Preorder traversal for serializing the binary tree, So we will use the same traversal for converting string back to Binary tree.

1. We will convert the String into array for accessing Node data.


2. Start reading array element and for each element create a new Node.
   (Because in Pre order traversal we first read Node data.)


3. Next element of array will be left child of newly created Node.
   (Because in Pre order traversal we keep reading Left Subtree until we encounter null Node.)


4. After Left subtree is completed, Next element of array will be Right child of newly created Node.
   (Because in Pre order traversal after left subtree, we keep reading Right Subtree until we encounter null Node.)

Let's see how recursion tree looks like,

By reading the serialized String[] array, we will recreate original Binary Tree back.
We will recursively read the String[] and create the tree.

For reading the string array, we need to keep track of which array index to read next.

For tracking which array index to read next, we are taking index array which holds only one element which keep track of next element to read. 
We are taking index array and updating value inside it because updating array value will persist across recursive call.

Note: we can't take "int index" for this purpose, because we are using recursion, so whenever we will backtrack we will lose the next updated index to read.
There are other ways to achieve the same functionality like taking static index variable etc.

Serialize Deserialize Binary Tree Java Program

---

package com.javabypatel.tree;

/*

Input:
                 10
              /      \
             5       20
           /  \
          3   8
             /
            7
Output:
    Preorder = 10,5,3,null,null,8,7,null,null,null,20,null,null,
    Tree:
                 10
              /      \
             5       20
           /  \
          3   8
             /
            7
*/
public class SerializeAndDeserializeBinaryTree {

    public static void main(String[] args) {

        Node rootNode = null;
        rootNode = addNode(rootNode, 10, true);
        rootNode = addNode(rootNode, 5, true);
        rootNode = addNode(rootNode, 20, true);
        rootNode = addNode(rootNode, 3, true);
        rootNode = addNode(rootNode, 8, true);
        rootNode = addNode(rootNode, 7, true);

        printTreePreOrder(rootNode);
        System.out.println();

        String str = serializeBinaryTree(rootNode);
        System.out.println(str);

        Node start = deserializeBinaryTree(str);
        System.out.println(start);
        printTreePreOrder(start);
    }

    //Serialize Binary Tree
    private static String serializeBinaryTree(Node rootNode) {
        if (rootNode == null) {
            return "null,";
        }

        StringBuilder sb = new StringBuilder();
        sb.append(rootNode.getData());
        sb.append(",");

        sb.append(serializeBinaryTree(rootNode.getLeft()));
        sb.append(serializeBinaryTree(rootNode.getRight()));
        return sb.toString();
    }

    //Deserialize Binary Tree
    public static Node deserializeBinaryTree(String data) {
        String[] temp = data.split(",");
        //return deserialize(temp, new int[] {0});
        return deserializeUsingStaticCounter(temp);
    }

    private static Node deserialize(String[] data, int[] index) {
        if (index[0] > data.length || data[index[0]].equals("null")) {
            index[0]++;
            return null;
        }

        //After reading the data, increment index value as indication to read next
        //array value in further iteration
        Node node = new Node(Integer.parseInt(data[index[0]++]));
        node.setLeft(deserialize(data, index));
        node.setRight(deserialize(data, index));

        return node;
    }

    static int index;

    private static Node deserializeUsingStaticCounter(String[] data) {
        if (index > data.length || data[index].equals("null")) {
            index++;
            return null;
        }

        Node node = new Node(Integer.parseInt(data[index++]));
        node.setLeft(deserializeUsingStaticCounter(data));
        node.setRight(deserializeUsingStaticCounter(data));

        return node;
    }

    private static Node addNode(Node rootNode, int i, boolean isRootNode) {
        if (rootNode == null) {
            return new Node(i);
        } else {
            if (i > rootNode.getData()) {
                if (isRootNode) {
                    Node nodeToAdd = addNode(rootNode.getRight(), i, isRootNode);
                    rootNode.setRight(nodeToAdd);
                } else {
                    Node nodeToAdd = addNode(rootNode.getLeft(), i, isRootNode);
                    rootNode.setLeft(nodeToAdd);
                }

            } else {
                if (isRootNode) {
                    Node nodeToAdd = addNode(rootNode.getLeft(), i, isRootNode);
                    rootNode.setLeft(nodeToAdd);
                } else {
                    Node nodeToAdd = addNode(rootNode.getRight(), i, isRootNode);
                    rootNode.setRight(nodeToAdd);
                }
            }
        }
        return rootNode;
    }

    private static void printTreePreOrder(Node rootNode) {
        if (rootNode == null)
            return;
        System.out.print(rootNode.getData() + " ");
        printTreePreOrder(rootNode.getLeft());
        printTreePreOrder(rootNode.getRight());
    }
}

Node.java

package com.javabypatel.tree;

public class Node {

    private Node left;
    private Node right;
    private int data;

    public Node(int data) {
        this.data = data;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }
}

You may also like to see

---

Top Binary tree interview questions in Java

Find Kth SMALLEST element in BST(Binary Search Tree)

Check whether Binary Tree is foldable or not.

Check if two nodes are cousins in a Binary Tree.

Get Level/Height of node in binary tree

Print nodes at K distance from Leaf node in Binary tree.

Construct a Binary Tree from In-order and Post-order traversals.

Print Nodes in Top View of Binary Tree.

Zig Zag Traversal of Binary Tree.

Convert Sorted Array to Balanced Binary Search Tree

Print Nodes visible from Bottom View of Binary Tree.

Connect nodes at same level in binary tree using constant extra space.

Multithreading Interview Questions-Answers