Java Code for Serialization and Deserialization

The Java code for both serialization (treeToArray method) and deserialization (arrayToTree method) is given below. For the treeToArray method, I have used an ArrayList object to add keys to the list. ArrayList is a convenient data structure to use if we don't know the size of the array in advance.

Note that for all the recursive routines, we need a public function to be called from outside the class and a corresponding helper function.

Wrapping it up

I hope you enjoyed working on this problem. Note, preorder traversal is not the only method of serialization. You can use methods based on inorder or postorder traversal. You can also use a level order traversal if you wish. Do try this out for different trees and see how the recursion is working. If n is the number of keys in the tree, then both serialization and deserialization have a complexity of O(n), as each key is traversed only once. Also, the array for storing the binary tree requires O(n) space as all keys in addition of null links are stored. Even if the links are double the size of total keys, the space complexity remains O(n).

xxxxxxxxxx

}

import java.util. * ;

import java.lang. * ;

//binary tree class

class node {

  int key;

  node left;

  node right;

  public node(int k) {

    key = k;

  }

  public void setLeft(int x) {

    left = new node(x);

  }

  public void setRight(int x) {

    right = new node(x);

  }

​

}

​

class binaryTree {

  node root;

  int ind;

​

  public int[] treeToArray() {

    //we'll create an array list and then convert it to array

    //as we don't know in advance how many keys have to be stored

    ArrayList < Integer > arrList = new ArrayList < Integer > ();

    //call helper that recursively adds to array

    treeToArray(root, arrList);