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

def serilized_helper(res, root):
    if not root:
        res.append("#")
    else:
        res.append(str(root.val))
        serilized_helper(res, root.left)
        serilized_helper(res, root.right)

def serilized_tree(root):
    res = []
    serilized_helper(res, root)
    return " ".join(res)

def deserilized_helper(tree_iter):
    val = next(tree_iter)
    if val == "#":
        return None
    node = Node(int(val))
    node.left = deserilized_helper(tree_iter)
    node.right = deserilized_helper(tree_iter)
    return node

def deserilized_tree(tree_str):
    tree_str_iter = iter(tree_str.split(" "))
    root = deserilized_helper(tree_str_iter)
    return root

def preorder_traversal_helper(res, root):
    if not root:
        return
    res.append(root.val)
    preorder_traversal_helper(res, root.left)
    preorder_traversal_helper(res, root.right)

def preorder_traversal(root):
    res = []
    preorder_traversal_helper(res, root)
    return res

def inorder_traversal_helper(res, root):
    if not root:
        return
    inorder_traversal_helper(res, root.left)
    res.append(root.val)
    inorder_traversal_helper(res, root.right)

def inorder_traversal(root):
    res = []
    inorder_traversal_helper(res, root)
    return res

def main():
    n1 = Node(1)
    n2 = Node(-2)
    n3 = Node(3)
    n4 = Node(4)
    n5 = Node(5)

    n1.left = n2
    n1.right = n3
    n3.left = n4
    n3.right = n5

    tree_str = serilized_tree(n1)
    print(tree_str)
    expected_tree_str = "12##34##5##"
    if tree_str == expected_tree_str:
        print("Serilized succeed.")

    # check if deserilized succeed.
    print("Preorder traversal. Be caution only preorder can't identify a tree")
    print(preorder_traversal(n1))
    print("Inorder traversal.")
    print(inorder_traversal(n1))

    new_root = deserilized_tree(tree_str)
    print("Deserilized tree preorder traversal")
    print(preorder_traversal(new_root))
    print("Deserilized tree inorder traversal")
    print(inorder_traversal(new_root))

if __name__ == "__main__":
    main()