# DS Blank, Fall 2010, Data Structures
# Questions 1 and 2 Solutions

import random

class Tree:
    def __init__(self, value=None):
        self.value = value
        self.left = None
        self.right = None

    def insert(self, value):
        if value < self.value:
            # insert on left
            if self.left == None:
                self.left = Tree(value) 
            else:
                self.left.insert(value)
        else:
            # insert on right
            if self.right == None:
                self.right = Tree(value) 
            else:
                self.right.insert(value)

    def contains(self, value, count=0):
        if value == self.value:
            return (True, count + 1)
        elif value < self.value:
            if self.left is None:
                return (False, count + 1)
            return self.left.contains(value, count + 1)
        elif value > self.value:
            if self.right is None:
                return (False, count + 1)
            return self.right.contains(value, count + 1)

    def to_list(self):
        retval = []
        if self.left is not None:
            retval += self.left.to_list()
        retval += [self.value]
        if self.right is not None:
            retval += self.right.to_list()
        return retval

    def from_list(self, list):
        if len(list) != 0:
            pos = len(list)//2
            left = list[:pos]
            right = list[pos+1:]
            if self.value == None:
                self.value = list[pos]
            else:
                self.insert(list[pos])
            self.from_list(left)
            self.from_list(right)

    def size(self):
        if self.left == None:
            left = 0
        else:
            left = self.left.size()
        if self.right == None:
            right = 0
        else:
            right = self.right.size()
        return left + right + 1

def makeRandom(max_value=100000000):
    return int(random.random() * max_value)

tree1 = Tree(makeRandom())
for i in range(999):
    tree1.insert(makeRandom())

print tree1.contains(654)

items = tree1.to_list()
tree2 = Tree()
tree2.from_list(items)