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 :
Top comments (7)
In Serializing, you are calling
inorder(root);. You wantpreorder(root)?Yeah, typo. My bad. Thanks for pointing out :)
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.
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.
You can use whitespace instead of X, it makes you decision more readble
and your comment still says //standard inorder traversal.
copy paste error? LOL
my bad