implementation of binary search tree in python

Simply put, a binary tree is a data structure in which each node has at most two children.

Binary search tree on the other hand has some specific properties which enable this data structure to be efficient executing operations like insert, delete, lookup ... 

Generally our binary search tree implementation satisfies following:

• One node is designated the root of the tree.
• Each internal node contains a key and has two subtrees.
• The leaves (final nodes) of the tree contain no key. Leaves are commonly represented by a special leaf or nil symbol, a NULL pointer, etc.
• Each subtree is itself a binary search tree.
• The left subtree of a node contains only nodes with keys strictly less than the node's key.
• The right subtree of a node contains only nodes with keys strictly greater than the node's key.

Our implementation is regular search tree. It doesn't guarantee efficiency of order O(log(n)) for worst case scenario like AVL trees (balanced trees).

Little about efficiency:

Insertion - worst case time complexity is of order O(n) -> when tree deforms to list.
Example would be if all elements in ascending or descending order.

| 1 2 3 4 12 525 535 ... OR 82 72 61 2 1 ...

However, in average case, time complexity of insertion would be of order O(log(n)) which is very good.

Same applies to delete operation and lookup operation.

Note: Actually for the sake of precision, search (lookup) operation is of order O(log(n)) -- in average case. Insertion in itself requires us to find a position for that element (search procedure) and the insert desired element, same for deletion. Inserting a node after we've found it's place is of order O(1) -- constant time. 


To implement this data structure in python we will define two classes, class Node will represent our nodes and information every node contains and other class Tree which will be class implementing our binary tree. We use classes since python doesn't provide structs like c.

Implementation is recursive as it is natural for binary search tree by definition.

Node class consists of attributes l, r, v -- which represents "pointers to" left and right child and v -- representing value or key our node contains.

class Node:
    def __init__(self, val):
        self.l = None
        self.r = None
        self.v = val

  Now we define class Tree like so:

class Tree:
    def __init__(self):
        self.root = None

    def getRoot(self):
        return self.root

    def add(self, val):
        if(self.root == None):
            self.root = Node(val)
        else:
            self._add(val, self.root)

    def _add(self, val, node):
        if(val < node.v):
            if(node.l != None):
                self._add(val, node.l)
            else:
                node.l = Node(val)
        else:
            if(node.r != None):
                self._add(val, node.r)
            else:
                node.r = Node(val)

    def find(self, val):
        if(self.root != None):
            return self._find(val, self.root)
        else:
            return None

    def _find(self, val, node):
        if(val == node.v):
            return node
        elif(val < node.v and node.l != None):
            self._find(val, node.l)
        elif(val > node.v and node.r != None):
            self._find(val, node.r)

    def deleteTree(self):
        # garbage collector will do this for us. 
        self.root = None

    def printTree(self):
        if(self.root != None):
            self._printTree(self.root)

    def _printTree(self, node):
        if(node != None):
            self._printTree(node.l)
            print str(node.v) + ' '
            self._printTree(node.r)
class='hljs python'

method printTree is for testing, in order to test this code we make an instance of our tree class.
Here it is...

tree = Tree()
tree.add(3)
tree.add(4)
tree.add(0)
tree.add(8)
tree.add(2)
tree.printTree()
print (tree.find(3)).v
print tree.find(10)
tree.deleteTree()
tree.printTree()

Notice that following insertion order our tree should look like this:

     3
    / \
   0   4
    \   \
    2    8

In printTree function we've implemented lRr -- meaning left child, root, right child traversal. 
For practice you can add other tree traversals and implement delete specific node function.

So the full code ready for testing:

#!/usr/bin/python

class Node:
    def __init__(self, val):
        self.l = None
        self.r = None
        self.v = val

class Tree:
    def __init__(self):
        self.root = None

    def getRoot(self):
        return self.root

    def add(self, val):
        if(self.root == None):
            self.root = Node(val)
        else:
            self._add(val, self.root)

    def _add(self, val, node):
        if(val < node.v):
            if(node.l != None):
                self._add(val, node.l)
            else:
                node.l = Node(val)
        else:
            if(node.r != None):
                self._add(val, node.r)
            else:
                node.r = Node(val)

    def find(self, val):
        if(self.root != None):
            return self._find(val, self.root)
        else:
            return None

    def _find(self, val, node):
        if(val == node.v):
            return node
        elif(val < node.v and node.l != None):
            self._find(val, node.l)
        elif(val > node.v and node.r != None):
            self._find(val, node.r)

    def deleteTree(self):
        # garbage collector will do this for us. 
        self.root = None

    def printTree(self):
        if(self.root != None):
            self._printTree(self.root)

    def _printTree(self, node):
        if(node != None):
            self._printTree(node.l)
            print str(node.v) + ' '
            self._printTree(node.r)


tree = Tree()
tree.add(3)
tree.add(4)
tree.add(0)
tree.add(8)
tree.add(2)
tree.printTree()
print (tree.find(3)).v
print tree.find(10)
tree.deleteTree()
tree.printTree()

Hope that helps if you had some problems implementing binary search tree in python!