DEV Community

Akhil
Akhil

Posted on

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
Enter fullscreen mode Exit fullscreen mode

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';
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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"
Enter fullscreen mode Exit fullscreen mode
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..
Enter fullscreen mode Exit fullscreen mode

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);
};
Enter fullscreen mode Exit fullscreen mode

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);
};
Enter fullscreen mode Exit fullscreen mode

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 :

Latest comments (7)

Collapse
 
vraghuvamshi profile image
Vinayak Raghuvamshi

I have seen candidates appearing for interview and pretty much copy pasting the code from here or from Leetcode without much further thought. This is a bad practice.

Anybody reading about these solutions and preparing for an interview should bear in mind that it is not sufficient to just memorize and recite the code during interviews. Especially at Amazon. You need to actually understand it thoroughly and be able to ask yourself deeper questions. For example, why choose a String type to hold the serialized value? what are the drawbacks? etc.

Collapse
 
akhilpokle profile image
Akhil

well, that's why I am writing it as a blog so that I can understand the concepts at a much deeper level, break it down into simpler visual parts and share my learning.

Collapse
 
vraghuvamshi profile image
Vinayak Raghuvamshi

and your comment still says //standard inorder traversal.

copy paste error? LOL

Collapse
 
akhilpokle profile image
Akhil

my bad

Collapse
 
sm1le291 profile image
inesterov

You can use whitespace instead of X, it makes you decision more readble

Collapse
 
ronakjethwa profile image
Ronak Jethwa • Edited

In Serializing, you are calling inorder(root);. You want preorder(root)?

Collapse
 
akhilpokle profile image
Akhil

Yeah, typo. My bad. Thanks for pointing out :)