import hashlib


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


def build_tree(in_order, pre_order, in_strt, in_end):
    if in_strt > in_end:
        return None

    node = Node(pre_order[build_tree.pre_index])
    build_tree.pre_index += 1

    if in_strt == in_end:
        return node

    in_index = search(in_order, in_strt, in_end, node.data)

    node.left = build_tree(in_order, pre_order, in_strt, in_index - 1)
    node.right = build_tree(in_order, pre_order, in_index + 1, in_end)

    return node


def search(arr, start, end, value):
    for i in range(start, end + 1):
        if arr[i] == value:
            return i


def get_leaf_nodes(node, data_list):
    if node is None:
        return

    if node.left is None and node.right is None:
        data_list.append(node.data)

    get_leaf_nodes(node.left, data_list)
    get_leaf_nodes(node.right, data_list)

    return data_list


def read_order_file(file):
    order_list = []
    for line in open(file, 'r'):
        for word in line.split(" "):
            order_list.append(word)

    return order_list

# in_order = [11, 0, 1, 13, 7, 12, 10, 2, 9, 3, 8, 1, 4]
# pre_order = [2, 1, 0, 11, 7, 13, 10, 12, 3, 9, 1, 8, 4]

in_order = read_order_file('/home/milos/Downloads/challenge/inorder.txt')
pre_order = read_order_file('/home/milos/Downloads/challenge/preorder.txt')

build_tree.pre_index = 0
root = build_tree(in_order, pre_order, 0, len(in_order) - 1)

list = get_leaf_nodes(root, [])
print(hashlib.md5(''.join(map(str, list)).encode('utf-8')).hexdigest())