How to implement a binary search tree in Python?

Question

This is what I've got so far but it is not working:

class Node:     rChild,lChild,data = None,None,None      def __init__(self,key):         self.rChild = None         self.lChild = None         self.data = key  class Tree:     root,size = None,0     def __init__(self):         self.root = None         self.size = 0      def insert(self,node,someNumber):         if node is None:             node = Node(someNumber)         else:             if node.data > someNumber:                 self.insert(node.rchild,someNumber)             else:                 self.insert(node.rchild, someNumber)         return  def main():     t = Tree()     t.root = Node(4)     t.root.rchild = Node(5)     print t.root.data #this works     print t.root.rchild.data #this works too     t = Tree()     t.insert(t.root,4)     t.insert(t.root,5)     print t.root.data #this fails     print t.root.rchild.data #this fails too  if __name__ == '__main__':      main() 

Answer 1

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 = val  def 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: 1 3 5 7 pre order 3 1 7 5 

Answer 2

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 = lChild  class 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)