Daily Coding Problem #3
Tags: dev, practice, algorithms, challenge
Published: 2018-11-26 06:24:22

---
title: Daily Coding Problem #3
published: true
description: Daily Coding Problem sends you a coding task every day for you to practice for coding interview tasks
tags: 
- dev
- practice
- algorithms
- challenge
---

For quite some time I found my time procastinating after getting home from work. Untill a few days ago I stumbled upon the [Daily Coding Problem](https://www.dailycodingproblem.com/) (DCP) and decided to give it a shot. 
The code is in C#.

## How it works?
The folks at DCP send you a problem that was asked at a top company everyday for you to solve. The premium membership also offers the opportunity to verify your solution.

# Problem #2
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.

For example, given the following Node class

class Node: def init(self, val, left=None, right=None): self.val = val self.left = left self.right = right The following test should pass:

node = Node('root', Node('left', Node('left.left')), Node('right')) assert deserialize(serialize(node)).left.left.val == 'left.left'

# My solution
```
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Task03
{
	public class Program
	{
		private const string Empty_Marker = "1";

		public static void Main(string[] args)
		{
			var node = new Node("root", new Node("left", new Node("left.left")), new Node("right"));

			var serialized = Serialize(node);

			Console.WriteLine(serialized);
			node = Deserialize(serialized);

			Console.WriteLine(node.Left.Left.Value);
		}

		public static string Serialize(Node node)
		{
			if (node == null)
			{
				return Empty_Marker + '-';
			}

			var builder = new StringBuilder();

			builder.Append($"{node.Value}-");

			builder.Append(Serialize(node.Left));
			builder.Append(Serialize(node.Right));

			return builder.ToString();
		}

		public static Node Deserialize(string serializedNode)
		{
			var nodes = serializedNode
				.Split('-', StringSplitOptions.RemoveEmptyEntries)
				.ToArray();

			var queue = new Queue<string>(nodes);

			var node = DeserializeNode(queue);

			return node;
		}

		private static Node DeserializeNode(Queue<string> nodes)
		{
			if (nodes.Peek() != null)
			{
				var nextNode = nodes.Dequeue();

				if (nextNode == Empty_Marker)
				{
					return null;
				}

				var node = new Node(nextNode);

				node.Left = DeserializeNode(nodes);

				node.Right = DeserializeNode(nodes);

				return node;
			}

			return null;
		}
	}
```

# Explanation
For the serialization, we traverse the tree depth first and add the current node's value to the serialized string. When we reach a node which is null (basically it's parent doesn't have a child), we put an `Empty_Marker` to signal that there is no node here. This works assuming the symbols for `Empty_Marker` and '-' are not going to be used in any node's value.

For the deserialize, we split the given string and put the results in a queue. Then build the tree depth first, getting through the queue's first element and stopping when we reach an `Empty_Marker`

I will try to do the daily problem everyday, but sometimes life gets in the way :)
Solutions are posted in my github account

{% github cwetanow/DailyCodingProblem %}. 

Feel free to leave a like and let me know in the comments if I should continue to post my solutions.

If you also have any better solution in mind, by all means share it, so we can learn from each other.