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 (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