Tree

tree.py

#TODO: insert, delete

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

def depth(root, depth=0):
    if root.left:
        depth = max(depth, depth(root.left))
    if root.right:
        depth = max(depth, depth(root.right))
    return depth + 1

def print_inorder(item):
    if item:
        print_inorder(item.left)
        print item.data
        print_inorder(item.right)

def print_preorder(item):
    if item:
        print item.data
        print_preorder(item.left)
        print_preorder(item.right)

def print_postorder(item):
    if item:
        print_postorder(item.left)
        print_postorder(item.right)
        print item.data

def bfs(graph, start, path=[]):
    queue = [start]
    while queue:
        #visited will always have one element
        visited = queue.pop(0)
        if visited not in path:
            path += [visited]
            # added so that dict doesnt give keyerror
            if visited in graph:
                queue += graph[visited]
    return path

def dfs(graph, start, path=[]):
    queue = [start]
    while queue:
        visited = queue.pop(0)
        if visited not in path:
            path += [visited]
            if visited in graph:
                queue = graph[visited] + queue
    return path

def print_depthwise(item, list_of_lists=[]):
    list = [item]
    while list:
        list_of_lists.append([e.data for e in list])
        list = [e.left for e in list if e.left] + \
               [e.right for e in list if e.right]
    return list_of_lists

def tree_to_dict(item, dict={}):
    values = []
    if item:
        if item.left:
            values.append(item.left.data)
        if item.right:
            values.append(item.right.data)
        if values != []:
            dict[item.data] = values
        tree_to_dict(item.left)
        tree_to_dict(item.right)
    return dict

def search(item, val):
    if item:
        if item.data == val:
            return item
        elif item.data < val:
            return search(item.right, val)
        elif item.data > val:
            return search(item.left, val)
    return False

root = Node('15')
root.right = Node('26')
root.left = Node('9')
root.left.left = Node('8')
root.right.right = Node('32')
root.right.left = Node('21')

#print_inorder(root)
#print_preorder(root)
#print_postorder(root)
#graph = tree_to_dict(root)
#print bfs(graph, '15')
#print dfs(graph, '15')
#print search(root, '32')
print print_depthwise(root)