Serialize and Deserialize binary tree, Apple interview

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.

1 > Serializing the Binary Tree to string

How to traves the tree

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 :

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.

How to convert and store nodes to string

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 :

   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 :

   const NULL = 'NN'; // NN = null node

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


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;
};

2 > Deserializing the string to Binary Tree

Splitting the string

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

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

Using the data to build the tree

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 :


    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 :

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 :

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 :

Blog