Ivan

Posted on

# Daily Coding Problem #3

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

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;

{
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.

Tiago Romero Garcia • Edited

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"

``````

Levi Ermonaites De Freitas

Exactly man, I looked at it, and thought, what?? They're asking one thing that already exists?

E. Choroba • Edited

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/\$_->[0]/\\\$_->[1]/g
for [qr/\\/ => '\\'],
[qr/"/  => '\''],
[qr/\(/ => '['],
[qr/\)/ => ']'];

return \$value
};

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

\$value =~ s/(?<!\\)\\\$_->[0]/\$_->[1]/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';
``````

Benjamin Braatz • Edited

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.

Solomon Li ✊YOLO🙃

Quite impressive, thank you!

I think this is a minimal and fast solution :

``````import re

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

def serialize(root: Node) -> str:
if root is None:
return ""
return f"({root.val},{serialize(root.left)},{serialize(root.right)})"

def deserialize(serialized: str) -> Node:
if serialized is None:
return None
match = re.search(r"\(([\w\.]+),(\(.*\))?,(\(.*\))?\)", serialized)
if match:
val, left, right = match.groups()
return Node(val=val, left=deserialize(left), right=deserialize(right))

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

``````

Jay

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[0]

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('-')[0];

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)));
}
}
}
``````

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'
``````

Solomon Li ✊YOLO🙃

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

DEV Community