Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists).

__author__ = 'nitin'

class BinaryTree:
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None

    def insertLeft(self,newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.leftChild = self.leftChild
            self.leftChild = t

    def insertRight(self,newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.rightChild = self.rightChild
            self.rightChild = t

    def getRightChild(self):
        return self.rightChild

    def getLeftChild(self):
        return self.leftChild

    def setRootVal(self,obj):
        self.key = obj

    def getRootVal(self):
        return self.key

def max_depth(root):
    if root is None:
        return 0
    else:
        return 1 + max(max_depth(root.getLeftChild()),max_depth(root.getRightChild()))

def find_level_list(root):
    level=0
    depth=max_depth(root)
    print depth
    result=[[] for x in xrange(depth)]
    tmp_list=[]
    tmp_list.append(root)
    result[level]=tmp_list
    while True:
        tmp_list=[]
        i=0
        while i            n=result[level][i]
            if n is not None:
                if n.getLeftChild() is not None:
                    tmp_list.append(n.getLeftChild())
                if n.getRightChild() is not None:
                    tmp_list.append(n.getRightChild())
            i=i+1
        if len(tmp_list)>0:
            result[level+1]=tmp_list
        else:
            break
        level=level +1
    return result

r = BinaryTree('a')
r.insertLeft('b')
r.insertRight('c')
r.insertLeft('d')

print find_level_list(r)