from bt_node import *
import random

'''A module for building and printing a binary tree.'''

def insert_node(data, root):
    '''Insert data into the binary tree rooted at root.
    Precondition: root is not None.'''
    node = root
    
    # Always insert the data in the rightmost node.
    while node.right is not None:
        node = node.right
    
    # Now node is not None, but node.right is None.
    node.right = BTNode(data)


def print_tree(root):
    '''Print the tree rooted at root.'''
    print_helper(root, "")


def print_helper(root, indent):
    '''Print the tree rooted at BTNode root. Print str indent (which
    consists only of whitespace) before the root value; indent more for the
    subtrees so that it looks nice.'''
    if root is not None:
        print indent + str(root.key)
        print_helper(root.left, indent + "   ")
        print_helper(root.right, indent + "   ")


if __name__ == '__main__':
    '''At first, we want to require our trees to be non-empty. We'll start
    off with a tree containing just one node, with the data value 1.'''
    
    # "Random" numbers in programs are usually not entirely random: each
    # random number is calculated from the previous one, so if you know the
    # initial number, you can predict the sequence. The following function
    # call starts the sequence off at the same place every time, which is
    # useful during debugging.
    random.seed(0.1)
    
    root = BTNode(1)
    
    # Write code here to read integers from the keyboard (using raw_input)
    # and insert each integer into a binary tree of BTNodes. Stop processing
    # input when the user enters an empty string.
    
    print '----'
    
    #  Print the tree.
    
    print_tree(root)