from random import randint

# Description of a node
class TreeNode (object):
  def __init__ (self, value = None):
    self.value = value
    self.left = None
    self.right = None

"""
  This function defines a root for the tree and initiates
  the process of looping through the values and inserting
  them into the tree.
"""
def make_tree (values):
  tree = None

  for value in values:
    tree = insert(tree, value)

  return tree

"""
  Adds a node to the tree
"""
def insert (root, value, key = lambda value: value):
  # Test whether there is a node at the current location
  if not root:
    # If not, insert the node here

    root = TreeNode()
    root.value = value
  else:
    # There is a node, compare value to be inserted
    # and the value of the node to decide whether the
    # node should be attached to the left or the right
    if key(value) < key(root.value):
      root.left = insert(root.left, value, key)
    else:
      root.right = insert(root.right, value, key)
  return root

"""
  Measures the depth of a (sub)tree
"""
def measure_tree (node):
  if node:
    # If there is a node, measure the depth
    # of the left and right node
    depth_left = measure_tree(node.left)
    depth_right = measure_tree(node.right)

    # Return the answer with the highest value
    # and add one
    return max(depth_left, depth_right) + 1
  else:
    # There isn't a node, answer with the value 0
    return 0


def traverse_tree (node):
  # Test whether there is a node
  if node:
    # If there is a node, ask its left node to traverse
    tree_left = traverse_tree(node.left)
    # and ask the same for its right node
    tree_right = traverse_tree(node.right)

    # Then combine into a new list:
    # the list answered by the left node
    # with the value of the node itself
    # And the list answered by the right node
    #
    # Give this new list as an answer to the root node
    return tree_left + [ node.value ] + tree_right
  else:
    # There is no node, return an empty list
    return []


if __name__ == '__main__':
  values = [randint(0, 100) for _ in range(15)]
  tree = make_tree(values)

  print(values, tree.value, tree.left.value if tree.left else None, tree.right.value if tree.right else None, measure_tree(tree), traverse_tree(tree))