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

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

def traverse (node, stack = None):
    if stack is None:
        stack = []

    if node.left and node.left.visited == False:
        stack.append(node.left)
        print(node.left.data)
        node.left.visited = True
        traverse(node.left)

    if node.right and node.right.visited == False:
        stack.append(node.right)
        print(node.right.data)
        node.right.visited = True
        traverse(node.right)

    else :
        if len(stack) > 0:
            traverse(stack[len(stack)-1])
            stack.pop()

root = Node(6)
node_two = Node(2)
node_seven = Node(7)
node_one = Node(1)
node_four = Node(4)
node_three = Node(3)
node_five = Node(5)
node_six = Node(6)
node_nine = Node(9)


root.left = node_two
root.right = node_seven

node_two.left = node_one
node_one.right = node_four

node_four.right = node_three
node_three.right = node_five

node_seven.left = node_six
node_six.right = node_nine

traverse(root)