# Daily Coding Problem #3

### Ivan github logo Nov 26 '18・1 min read

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

# DailyCodingProblem

This repository contains solutions of the Daily Coding Problem tasks

.

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.

DISCUSS (9) In Javascript, JSON serialization/unserialization is already supported, so this felt like cheating:

``````class Node {
constructor(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}

toString() {
return JSON.stringify(this);
}
};

const serialize = node => node.toString();
const deserialize = string => JSON.parse(string);

const node = new Node('root', new Node('left', new Node('left.left')), new Node('right'));

console.log(deserialize(serialize(node)).left.left.val); // prints "left.left"

``````

The tricky part is to make it work for arbitrary values, i.e. drop the assumption the symbols for Empty_Marker and '-' are not going to be used in any node's value.

Here's such a solution in Perl, tests included:

``````#!/usr/bin/perl
use warnings;
use strict;

package Node {
use Moo;

has value => (is => 'ro', required => 1);
has left  => (is => 'ro', isa => sub { shift->isa('Node') or die });
has right => (is => 'ro', isa => sub { shift->isa('Node') or die });

my \$_escape_value = sub {
my (\$self) = @_;
my \$value = \$self->value;
\$value =~ s/\$_->/\\\$_->/g
for [qr/\\/ => '\\'],
[qr/"/  => '\''],
[qr/\(/ => '['],
[qr/\)/ => ']'];

return \$value
};

my \$unescape = sub {
my (\$value) = @_;

\$value =~ s/(?<!\\)\\\$_->/\$_->/g
for [qr/\]/ => ')'],
[qr/\[/ => '('],
[qr/'/  => '"'];
\$value =~ s/\\\\/\\/g;

return \$value
};

my \$parse = sub {
my (\$rest) = @_;
my \$pos = '(' eq substr \$rest, 0, 1;
my \$rank = \$pos;
until (0 == \$rank) {
++\$rank if '(' eq substr \$rest, \$pos, 1;
--\$rank if ')' eq substr \$rest, \$pos, 1;
++\$pos;
}

my \$left  = substr \$rest, 0, \$pos;
my \$right = substr \$rest, \$pos + (\$pos != length \$rest);

length \$_ and \$_  = __PACKAGE__->deserialize(\$_)
for \$left, \$right;

return \$left, \$right
};

sub serialize {
my (\$self) = @_;

my \$value = \$self->\$_escape_value;
my (\$left, \$right) = map \$_ ? \$_->serialize : "",
\$self->left,
\$self->right;

return '(' . join(',', qq("\$value"), \$left, \$right) . ')'
}

sub deserialize {
my (\$class, \$string) = @_;

return undef unless length \$string;

my (\$value, \$rest) = \$string =~ /^\("([^"]*)",(.*)\)\$/sg;

\$value = \$unescape->(\$value);
my (\$left, \$right) = \$parse->(\$rest);

return \$class->new(value => \$value,
(left  => \$left)  x !! ref \$left,
(right => \$right) x !! ref \$right)
}

};

use Test::More tests => 7;

my \$node1 = 'Node'->new(
value => 'root',
left  => 'Node'->new(
value => 'left',
left => 'Node'->new(value => my \$left_left = 'left.left')),
right => 'Node'->new(value => 'right'),
);

is 'Node'->deserialize(\$node1->serialize)->left->left->value, \$left_left;

my \$node2 = 'Node'->new(
value => my \$empty = "",
right => 'Node'->new(value => my \$special_chars = '("[,\'\\]"))',
right => 'Node'->new(
value => my \$newline = "1\n2")));

is 'Node'->deserialize(\$node2->serialize)->value,
\$empty;
is 'Node'->deserialize(\$node2->serialize)->right->value,
\$special_chars;
is 'Node'->deserialize(\$node2->serialize)->right->right->value,
\$newline;

my \$node3 = 'Node'->new(value => \$node1->serialize,
left  => 'Node'->new(value => \$node2->serialize));

is 'Node'->deserialize(\$node3->serialize)->value,
\$node1->serialize;
is 'Node'->deserialize(\$node3->serialize)->left->value,
\$node2->serialize;

my \$super = \$node3->serialize;

\$super = 'Node'->new(
value => 'Node'->deserialize(\$super)->serialize
)->serialize
for 1 .. 6;

my \$root = \$super;
\$root = 'Node'->deserialize(\$root)->value for 1 .. 8;
is \$root, 'root';
``````

Python solution using recursion.

``````class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right

class Stringifier():
def __init__(self):
self.current = 0

def serialize(self, root, strTree = []):
if root is None:
return
strTree.append('{')
strTree.append('\"' + root.val + '\"')
self.serialize(root.left, strTree)
self.serialize(root.right, strTree)
strTree.append('}')
return "".join(strTree)

def _deserialize(self, strTree):
left = None
right = None
if strTree[self.current] == '{' :
self.current += 1
val = ""
if strTree[self.current] == '\"':
self.current += 1
while strTree[self.current] != '\"':
val += strTree[self.current]
self.current += 1
self.current += 1
if strTree[self.current] == '{':
left = self._deserialize(strTree)
if strTree[self.current] == '{':
right = self._deserialize(strTree)
if strTree[self.current] == '}':
self.current += 1
return Node(val, left, right)

def deserialize(self, strTree):
self.current = 0
return self._deserialize(strTree)

if __name__ == "__main__":
stringifier = Stringifier()
node = Node('root', Node('left', Node('left.left')), Node('right'))
assert stringifier.deserialize(stringifier.serialize(node)).left.left.val == 'left.left'
``````

Python solution defining `__repr__`, which is meant for exactly this purpose:

``````class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right

def __repr__(self):
return ( 'Node(' + repr(self.val) + ', '
+ repr(self.left) + ', '
+ repr(self.right) + ')' )

def __eq__(self, other):
if isinstance(other, Node):
return ( self.val == other.val and
self.left == other.left and
self.right == other.right )
return False

def __hash__(self):
return hash((self.val, self.left, self.right))

serialise = repr
deserialise = eval

node = Node('root', Node('left', Node('left.left')), Node('right'))
assert deserialise(serialise(node)).left.left.val == 'left.left'
assert deserialise(serialise(node)) == node
assert hash(deserialise(serialise(node))) == hash(node)
``````

Edit: Included test from problem statement in the code, so that it should now be ready for copy and paste into file and `python3 -i <file>`. While we are at it, implemented `__eq__` and `__hash__`, so that we can assert even stronger tests.

Quite impressive, thank you!

Go solution. Its a bit verbose as it does not have optional/default params.

``````package main

import (
"fmt"
"strings"
)

type Node struct {
val   string
left  *Node
right *Node
}

func (node *Node) serialize() string {
if node == nil {
return "#"
}

leftSide := node.left.serialize()
rightSide := node.right.serialize()

ret := fmt.Sprintf("%s->%s->%s", node.val, leftSide, rightSide)
return ret
}

func deserialize(str string) Node {
node, _ := deserailizeNodes(strings.Split(str, "->"))
return node
}

func deserailizeNodes(nodes []string) (Node, []string) {

if len(nodes) == 0 {
return Node{"", nil, nil}, nil
}

nextNode := nodes

if nextNode == "#" {
return Node{"", nil, nil}, nodes[1:]
}

left, rem := deserailizeNodes(nodes[1:])
right, _ := deserailizeNodes(rem)

if left.val == "" && right.val == "" {
return Node{nextNode, nil, nil}, nil
}
if left.val == "" {
return Node{nextNode, nil, &right}, nil
}
if right.val == "" {
return Node{nextNode, &left, nil}, nil
}

node := Node{val: nextNode, left: &left, right: &right}
return node, nil

}

func main() {
node := Node{"root", &Node{"left", &Node{"left.left", nil, nil}, nil}, &Node{"right", nil, nil}}
fmt.Println(node.serialize())
// root->left->left.left->#->#->#->right->#->#
n := deserialize(node.serialize())
fmt.Println(n.left.left.val == "left.left") // true
}

``````

Here's my C# solution

``````using System;

namespace DailyCodingProblem3
{
class Node
{
public string Val { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }

public Node(string val, Node left = null, Node right = null)
{
Val = val;
Left = left;
Right = right;
}
}

class Program
{
public static string Serialize(Node node)
{
if (node == null)
{
return "-";
}

string ret = \$"{node.Val}-";
ret += Serialize(node.Left);
ret += Serialize(node.Right);

return ret;
}

public static Node Deserialize(ref string str)
{
if (str.Length == 0 || str.StartsWith("-"))
{
return null;
}

var val = str.Split('-');

str = str.Substring(str.IndexOf('-') + 1);
var left = Deserialize(ref str);

str = str.Substring(str.IndexOf('-') + 1);
var right = Deserialize(ref str);

return new Node(val, left, right);
}

static void Main()
{
var node = new Node("root", new Node("left", null, new Node("left.right", new Node("left.right.left"))), new Node("right"));
var ret = Serialize(node);

Console.WriteLine(ret);
Console.WriteLine(Serialize(Deserialize(ref ret)));
}
}
}
``````

``````require 'json'

class Node
attr_accessor :v, :l, :r
def initialize(v, l=nil, r=nil)
self.v, self.l, self.r =
case v
when Hash
left, right =
%w|left right|.
map { |node| v[node] }.
map { |node| Node.new(node) unless node.to_s.empty? }
[v['value'], left, right]
when String
[v, l, r]
end
end

def to_s
%Q|{"value":"#{v}","left":#{l || '""'},"right":#{r || '""'}}|
end

def ==(other)
v == other.v && l == other.l && r == other.r
end
end

# test
nn = Node.new('root', Node.new('left', Node.new('left.left')), Node.new('right'))
Node.new(JSON.parse nn.to_s) == nn
#⇒ true
``````

Bonus: this serialization uses JSON format to make it easier to plug into other 3rd party code, if necessary.

My first time to see someone using Lua, thanks for the code, cool!

Classic DEV Post from Feb 15

## What was your win this week?

DEV is sort of like Medium, but it's open source and 100% focused on developers.

Now reaching over 3 million visitors per month, it's the fastest growing software development community in the world.

It's free, devoted to the open web, and will never have popups or a pay wall.  