Hello friends, in this series of solving the daily coding problem, here is daily coding problem – 3 whose solution I have shared in C# and Java.
This problem was asked by Google.
Given the root to a binary tree, implement serialize(root), which serializes the tree into a string, and deserialize(s), which deserializes the string back into the tree.
Daily coding problem – 3 Solution
For this coding problem we have been provided with a tree. As an example consider below is the example of the tree which we will be serializing into a string and de serializing back to tree.
Since we have to serialize a tree to a string, I think BFS is the best approach to achieve the same. As we need to de serialize it back to the tree.
Just for the representational purpose I have created the below screen shot for the problem. In the screen shot you can see there are nulls as well. This will help us to re create the tree.
Knowing that we have to use breadth first search, we have to maintain a queue in our solution which will keep track of the nodes we have to navigate.
Below is the C# code to Serialize a tree:
public static string serialize(TreeNode root)
{
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
StringBuilder sb = new StringBuilder();
while (queue.Count > 0)
{
root = queue.Dequeue();
TreeNode nextnode = null;
if (queue.Count > 0)
nextnode = queue.Peek();
if (root.left != null)
{
queue.Enqueue(root.left);
}
else if(root.val != -1 && (nextnode != null && (nextnode.left != null || nextnode.right != null)))
{
queue.Enqueue(new TreeNode(-1));
}
if (root.right != null)
{
queue.Enqueue(root.right);
}
else if (root.val != -1 && (nextnode != null && (nextnode.left != null || nextnode.right != null)))
{
queue.Enqueue(new TreeNode(-1));
}
if (root.val != -1)
{
sb.Append(root.val.ToString() + ",");
}
else
{
sb.Append("null,");
}
}
return sb.ToString().TrimEnd(',');
}Now if we have to de serialize the string separated by comma we can achieve the same by using the below code.
The main criteria to de serialize the string would be to create a tree. In the below code I am calling the method recursively.
public static TreeNode deserialize(string data)
{
string[] arrString = data.Split(',');
Queue<TreeNode> queue = new Queue<TreeNode>();
TreeNode node = new TreeNode(Convert.ToInt32(arrString[0]));
BuildTree(node, arrString, 1, arrString.Length);
return node;
}
private static void BuildTree(TreeNode node, string[] arrString, int v, int depthofTree)
{
if ((v * 2) < depthofTree)
{
int leftNodeIndex = 2 * v;
int rightNodeIndex = 2 * v + 1;
if (arrString[leftNodeIndex - 1].ToString() != "null")
{
node.left = new TreeNode(Convert.ToInt32(arrString[leftNodeIndex - 1]));
BuildTree(node.left, arrString, ++v, depthofTree);
}
if (arrString[rightNodeIndex - 1].ToString() != "null")
{
node.right = new TreeNode(Convert.ToInt32(arrString[rightNodeIndex - 1]));
BuildTree(node.right, arrString, ++v, depthofTree);
}
}
}Conclusion
While solving a problem we should have a clear understanding of all the data structures which can come handy to solve it.