DEV Community

Daily Coding Problem #3

Ivan on November 26, 2018

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

Read full post

Tiago Romero Garcia • Dec 5 '18 • 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 • Feb 18 '21

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

E. Choroba • Nov 26 '18 • 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 • Nov 28 '18 • 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🙃 • Mar 10 '19

Quite impressive, thank you!

Sajjad Dehghani • Mar 9 '20

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 • Nov 28 '18

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
}

Stefano Prosperi • Nov 27 '18 • Edited

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

Geoffrey Olson Jr. • Aug 20 '19 • Edited

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🙃 • Mar 10 '19

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