#From dailycodingproblem.com
#Problem from 5.9.2019
#My solution

#Good morning! Here's your coding interview problem for today.

#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:

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


def serialize( node ):
    nodes = []
    address_to_id = { id(node) : 1 }
    stack = [node]
    while stack:
        p = stack.pop()
        def app_child(ch):
            if None != ch:
                stack.append( ch )
                if id(ch) not in address_to_id:
                    address_to_id[id(ch)] = len(address_to_id) + 1
                return address_to_id[id(ch)]
            return 0;
        nodes.append( (
            address_to_id[id(p)],
            p.val,
            app_child(p.left),
            app_child(p.right)
        ) )
    return repr(nodes)

def deserialize( encoding ):
    node_map = {}
    for ( n_id, n_val, n_left, n_right ) in reversed(eval(encoding)):
        def get_node(i):
            if i == 0:
                return Node
            else:
                assert( i in node_map )
                return node_map[i]
        node_map[n_id] = Node( n_val, get_node(n_left), get_node(n_right) )
    assert( 1 in node_map )
    return node_map[1]



test()
print ("OK")