How to implement a binary search tree in Python?

Here is a quick example of a binary insert:

class Node:    def __init__(self, val):        self.l_child = None        self.r_child = None        self.data = valdef binary_insert(root, node):    if root is None:        root = node    else:        if root.data > node.data:            if root.l_child is None:                root.l_child = node            else:                binary_insert(root.l_child, node)        else:            if root.r_child is None:                root.r_child = node            else:                binary_insert(root.r_child, node)def in_order_print(root):    if not root:        return    in_order_print(root.l_child)    print root.data    in_order_print(root.r_child)def pre_order_print(root):    if not root:        return            print root.data    pre_order_print(root.l_child)    pre_order_print(root.r_child)    

r = Node(3)binary_insert(r, Node(7))binary_insert(r, Node(1))binary_insert(r, Node(5))

     3    / \   1   7      /     5

print "in order:"in_order_print(r)print "pre order"pre_order_print(r)in order:1357pre order3175

class Node:     rChild,lChild,data = None,None,None

This is wrong - it makes your variables class variables - that is, every instance of Node uses the same values (changing rChild of any node changes it for all nodes!). This is clearly not what you want; try

class Node:     def __init__(self, key):        self.rChild = None        self.lChild = None        self.data = key

now each node has its own set of variables. The same applies to your definition of Tree,

class Tree:    root,size = None,0    # <- lose this line!    def __init__(self):        self.root = None        self.size = 0

Further, each class should be a "new-style" class derived from the "object" class and should chain back to object.__init__():

class Node(object):     def __init__(self, data, rChild=None, lChild=None):        super(Node,self).__init__()        self.data   = data        self.rChild = rChild        self.lChild = lChildclass Tree(object):    def __init__(self):        super(Tree,self).__init__()        self.root = None        self.size = 0

Also, main() is indented too far - as shown, it is a method of Tree which is uncallable because it does not accept a self argument.

Also, you are modifying the object's data directly (t.root = Node(4)) which kind of destroys encapsulation (the whole point of having classes in the first place); you should be doing something more like

def main():    t = Tree()    t.add(4)    # <- let the tree create a data Node and insert it    t.add(5)

class Node:    rChild,lChild,parent,data = None,None,None,0    def __init__(self,key):    self.rChild = None    self.lChild = None    self.parent = None    self.data = key class Tree:    root,size = None,0    def __init__(self):        self.root = None        self.size = 0    def insert(self,someNumber):        self.size = self.size+1        if self.root is None:            self.root = Node(someNumber)        else:            self.insertWithNode(self.root, someNumber)        def insertWithNode(self,node,someNumber):        if node.lChild is None and node.rChild is None:#external node            if someNumber > node.data:                newNode = Node(someNumber)                node.rChild = newNode                newNode.parent = node            else:                newNode = Node(someNumber)                node.lChild = newNode                newNode.parent = node        else: #not external            if someNumber > node.data:                if node.rChild is not None:                    self.insertWithNode(node.rChild, someNumber)                else: #if empty node                    newNode = Node(someNumber)                    node.rChild = newNode                    newNode.parent = node             else:                if node.lChild is not None:                    self.insertWithNode(node.lChild, someNumber)                else:                    newNode = Node(someNumber)                    node.lChild = newNode                    newNode.parent = node                        def printTree(self,someNode):        if someNode is None:            pass        else:            self.printTree(someNode.lChild)            print someNode.data            self.printTree(someNode.rChild)def main():      t = Tree()    t.insert(5)      t.insert(3)    t.insert(7)    t.insert(4)    t.insert(2)    t.insert(1)    t.insert(6)    t.printTree(t.root)if __name__ == '__main__':    main()

My solution.