5. Serialize and Deserialize a binary tree

5. Serialize and Deserialize a binary tree

Tools

-Java 8
-CoderPad/SandBox

Solution

class Solution
     {
       public static void main(String[] args)
         {
         // Init a tree level 1
         Node root = new Node("root",null,null);
         root.right= new Node("righta",null,null);
         root.left= new Node("leftb",null,null);
         //Init tree level 2 left part
         root.right.right = new Node("righta.right",null,null);
         root.right.left= new Node("righta.left",null,null);
   
         //Init tree level 2 left part
         root.left.right=new Node("leftb.right",null,null);
   
         //Serialize the tree
         String res = Node.serialize(root);
         //Print the result
         System.out.println("Serialize: "+res);
         //Create a new tree from the Serialized tree
         Node root2 = Node.deSerialize(res);
         //Print the result. it must be similar to the previos tree
         System.out.print("Deserialize:");
         Node.print(root2);
       }
     }
     class Node
     {
       //Node Structure
         String value;
         Node right;
         Node left;
       //Empty construct
         public Node ()
         {
         }
       //Construct of a tree with values
         public Node(String value, Node left,Node right)
         {
           this.value = value;
           this.right=right;
           this.left=left;
         }
       //Serialize the tree
         public static String serialize (Node root)
         {
           //It uses a preorder method to serialize the tree
           return preorder(root,"",";root");
         }
         public static Node deSerialize(String tree)
         {
           /*
           Split the string into and array based on a regular expression. Don't forget to escape the separator, in mi case I used pipeline
           */
           String[] array = tree.split("\\|");
           //In first place, you need to send the method null, cero and the array
           Node root = preorderConstruct(null,0,array);
           return root;
         }
       /*
       Here node is the target node to evaluate
       String is the resulting string. The tree is serialing into it
       sense is the place that ocupes the target node into a previos node
       */
         public static String preorder(Node node, String string,String sense)
         {
           //Concatenate the resulting string to the new incoming values
           string = string + node.value+sense + "|";
           //Verify if there are nodes in tree. If true then move to left and get the string 
           if(node.left!=null)
           {
             string = preorder(node.left,string,";left");
           }
           //Verify if there are nodes in tree. If true then move to right and get the string
           if(node.right!=null)
           {
             string = preorder(node.right,string,";right");
           }
           // return string.
           return string ;
         }
       /*Method that re build the tree
       */
         public static Node preorderConstruct(Node prev,int index,String[]array)
         {
           //If index is less than lenght then do the precedure
           if(index < array.length)
           {
             //Get a node from the serializing string
             String sNode = array[index];
             //Split the node based on a regular expression
             String[] rNode = sNode.split(";");
             //Get the value and sense of the node based on a regular expression
             String value = rNode[0];
             String sense = rNode[1];
             //Create a new node with the values
             Node node = new Node(value,null,null);
             //If sense is equals to root then the previuos node must be the node that we created in the previous line
             if(sense.equals("root"))
             {
               prev = node;
             }
             //If sense is equals to left then we set the new node in the left side of the previous node
             if(sense.equals("left"))
             {
               prev.left= node;
             }
             //If sense is equals to left then we set the new node in the right side of the previous node
             if(sense.equals("right"))
             {
               prev.right= node;
             }
             //we send the new node, the increasing index by one and the array
             preorderConstruct(node,index+1,array);
           }
           return prev ;
         }
         public static void print(Node node)
         {
           System.out.print(node.value+"|");
           if(node.left!=null)
           {
             print(node.left);
           }
           if(node.right!=null)
           {
             print(node.right);
           }
         }
       }