Serialize and Deserialize binary tree, Apple interview
Tags: computerscience, career, webdev, javascript
Published: 2020-05-20 17:43:42

You might've used JSON.stringify and JSON.parse for storing data and retrieving data respectively. 

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Question: Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

This is one of those questions which is hard to put in words but when you'll look at the code, the thinking behind it comes intuitively, still I shall try my best to break it down.

<h3> 1 > Serializing the Binary Tree to string </h3> 

<h5> How to traves the tree </h5>
A binary tree is a type of Data Structure that consists of data, a left child, and a right child. There are various ways of parsing the tree. 

These are :
```javascript 
Inorder Traversal       : left child -> parent -> right child
Preorder Traversal      : parent -> left child -> right child 
Postorder Traversal     : left child -> right child -> parent
Depth-first Traversal   : parent -> left subTree -> rightSubTree
Breadth-First Traversal : parent Level -> Child level
```

So the plan is to use one of the traversal methods to traves each node in the tree, convert them to a string, and return that string. 

I went with Preorder since it's the easiest one to visualize what's happening. 

<h5> How to convert and store nodes to string </h5>

Converting nodes to string is simply appending the value of node data to the existing string.

Since each node has a left child and a right child we need some sort of splitter based on which we could differentiate between child nodes but at the same time while deserializing we want separate nodes based on this same splitter.

So we can do : 
```javascript 
   const SPLITTER = 'X';
```

After parsing each node, we shall append the SPLITTER.

Next, is how to store the "null" children? Since we can't ignore the null children as it will be hard keeping track of them which deserializing and since the given tree is not a "Binary Search Tree". 

So for storing null values : 
```javascript 
   const NULL = 'NN'; // NN = null node
``` 

Now we have our bit's and pieces, let combine them : 

```javascript

const SPLITTER = 'X';
const NULL = 'NN';

var serialize = function(root) {
    let serial = "";                 //start with empty string
    
    function preorder(root){
        if(root == null){ 
            serial += NULL + SPLITTER;       // add NULL + SPLITTER eg : 5X4XNNXNNX
            return;
        }
        serial += root.val + SPLITTER;       // add node + SPLITTER eg : 5X4X..
        
        // standard inorder travesal
        preorder(root.left);                  
        preorder(root.right);   
    }
    
    preorder(root);
    return serial;
};

```

<h3> 2 > Deserializing the string to Binary Tree </h3> 

<h5> Splitting the string </h5>

Since we get a string as input, we can use it to get individual nodes.

```javascript
   const data = input.split('X');            // "1X4XNNX".split('X')  -> "1","4","NN"
```  

<h5> Using the data to build the tree </h5> 

Since we used Preorder traversal to build the string, we shall use Preorder traversal to build the tree, and in the previous step, we split the string into each individual nodes, we will use a pointer to represent each node how ? Let see 

Also, As you remember, "null" represents the end of the left / right child of a node, so whenever we come across "NULL", we return "null". 

Now let Visualize this : 

```javascript 

    1
  /   \         becomes     "1X2XNNXNNX3XNNXNNX"     
 2     3

 "1X2XNNXNNX3XNNXNNX" when split becomes "1","2","NN","NN","3","NN","NN"

 Now use a pointer index, and build the tree

 index : 0  "1"         ->              1
 index : 1  "2"         ->              1
                                      /
                                     2
 index : 2  "NN"       ->                 1
                                        /
                                       2
                                      /
                                     null
 index : 3  "NN"       ->                 1
                                        /
                                       2
                                      /  \ 
                                     null null

 index : 4  "3"       ->                 1
                                        /  \
                                       2    3
                                      /  \ 
                                     null null

     and so on..
```

Converting the idea to code : 

```javascript
var deserialize = function(data) {
    data = data.split('X');                              //split the data
    let idx = 0;
    function buildTree(data){
        if(idx >= data.length) return null;              
        if(data[idx] == NULL){idx++; return null;}       // if NN return null 
        let node = new TreeNode(parseInt(data[idx++]));  // else create a new node
      
        //standar inorder travesal
        node.left = buildTree(data);
        node.right = buildTree(data);
        return node;
    }
    
    return buildTree(data);
};
```


Combining the two : 


```javascript
const SPLITTER = 'X';
const NULL = 'NN';
var serialize = function(root) {
    let serial = "";
    
    function inorder(root){
        if(root == null){ 
            serial += NULL + SPLITTER;
            return;
        }
        serial += root.val + SPLITTER;
        inorder(root.left);
        inorder(root.right);   
    }
    
    inorder(root);
    return serial;
};


var deserialize = function(data) {
    data = data.split('X');
    let idx = 0;
    function buildTree(data){
        if(idx >= data.length) return null;
        if(data[idx] == NULL){idx++; return null;}
        let node = new TreeNode(parseInt(data[idx++]));
        node.left = buildTree(data);
        node.right = buildTree(data);
        return node;
    }
    
    return buildTree(data);
};
```

I hope you understood my solution, these type of questions are a bit difficult to put in words but when you look at the code it becomes obvious, if you've doubts or if I messed up somewhere, please do comment.
github :https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/SerializeandDeserializeBinaryTree%2Cjs)

github :