from queue import Queue

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

    def __repr__(self):
        return str(self.data)

def construct_tree():
    print("construct_tree")
    return make_node(1,
                    make_node(2,
                            make_node(4,
                                    make_node(8, None, None),
                                    make_node(9, None, None)),
                            make_node(5,
                                    make_node(10, None, None),
                                    make_node(11, None, None))),
                    make_node(3,
                            make_node(6, None, None),
                            make_node(7,
                                    make_node(12, None, None),
                                    make_node(13, None, None))))

def make_node(data, left, right):
    node = Node()
    node.data = data
    node.left = left
    node.right = right
    if node.left:
        node.left.parent = node

    if node.right:
        node.right.parent = node

    return node

def print_level_order(root):
    """
    Traverses the tree and prints the data in each node in the order:
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
    """
    print("print_level_order")


print("Starting...")
root = construct_tree()

print_level_order(root)