Serialize and Deserialize a Binary Tree

Serialization is to store a tree in an array so that it can be later restored and
Deserialization is reading tree back from the array.

Note: The structure of tree must be maintained.

Solution:

• Process in PreOrder and mark null child with special marker (like -1)

Algorithm for serialize:

1. Traverse tree in preOrder
   1. If node is null then,
      1. list.add(-1)
      2. return
   2. list.add(node.data)
   3. Recursively call node left sub tree
   4. Recursively call node right sub tree

Algorithm for deserialize:

1. Create tree in PreOrder
   1. If counter >= list.size or list.get(counter) == -1 then
      1. return null
   2. Create node with list.get(counter)
   3. leftSubTree = recursively call with counter + 1
   4. rightSubTree = recursively call with counter + 2
   5. node.left = leftSubTree
   6. node.right = rightSubTree
   7. return node

Latest Source Code:
Github: BinaryTreeSerializeAndDeserialize.java

Output:

  Binary Tree : 
               25                               
              / \               
             /   \              
            /     \             
           /       \            
          /         \           
         /           \          
        /             \         
       /               \        
       18               50               
      / \             / \       
     /   \           /   \      
    /     \         /     \     
   /       \       /       \    
   19       20       35       60       
    \     / \     / \     / \   
     \   /   \   /   \   /   \  
     15   18   25   20   40   55   70   
                  \             
                  25             
                                                                

Serialized Tree :[25, 18, 19, -1, 15, -1, -1, 20, 18, -1, -1, 25, -1, -1, 50, 35, 20, -1, 25, -1, -1, 40, -1, -1, 60, 55, -1, -1, 70, -1, -1]

Deserialize Tree :
               25                               
              / \               
             /   \              
            /     \             
           /       \            
          /         \           
         /           \          
        /             \         
       /               \        
       18               50               
      / \             / \       
     /   \           /   \      
    /     \         /     \     
   /       \       /       \    
   19       20       35       60       
    \     / \     / \     / \   
     \   /   \   /   \   /   \  
     15   18   25   20   40   55   70   
                  \             
                  25