Binary Search Tree in Python  :

            Implementing the binary search tree in python looks hard job at the first sight if you are trying to transform your implementation from c/c++. Actually it is not, you can do it in an easy way.

What is Binary Search Tree :

                       Hope you are well-verse with the binary tree concepts.It's okay, just refresh it again here.THANKS for coming back again. Hope you gathered/refreshed the complete(somewhat) knowledge on binary search trees.Now we can proceed further. 

What's there in this article... ?

         Yes,I'm going to through some light on implementing the binary search tree in python. here you can get the implementation for insert, search and Traversal functions. Delete is in another article. Go for it as it's an interesting topic that i thought it must be discussed in a separate post.

A Sort Intro about My Implementation :

         Here I am going to use Node of a tree as an object . yes it is an object looks like this.
         class Node :
             def __ init__(self,data) :
                 self.data=data
                 self.left=None   #LeftChild - Initially None
                 self.right=None  #RightChild - Initially None
Now we just made the new node of our tree(consider).

Insertion is Easy as you think now... Yeah the procedure is as same as what we do in c/c++ but in python style.Decide where to insert the new node whether in the left or right. Once decided check if that node is None or not.If it is then just create a new object of the type Node class and assign the data.If not just make a recursive call with that node(usually SubTree).It looks something like this...
         def insert(self,data) : 
            if data < self.data :
                if self.left is None :
                    self.left=Node(data)
                else :
                    self.left.insert(data)
            elif data > self.data :
                if self.right is None :
                    self.right=Node(data)
                else :
                    self.right.insert(data)
Yes you are right, we just built a tree now. Tree Traversals are the easiest procedures to implement with recursion.I don't want to elaborate more on this topics.You just take a look at the code...
        def InOrder(self) :
            if self.left is not None :
                self.left.InOrder()
            sys.stdout.write(str(self.data)+" ")
            if not self.right is None :
                self.right.InOrder()
This is for preorder traversal of a tree...
       def PreOrder(self) :
           sys.stdout.write(str(self.data)+" ")
           if self.left is not None :
               self.left.PostOrder()
           if self.right is not None :
               self,right.PostOrder()
Please do the post order traversal yourself...
Now We just need to implement the search procedure,a hero of BST...It is so simple with recursion...I don't want to elaborate procedure as you already know how it has to be done. so please take a look at the code here...
       def Search_BST(self,data) :
           if self.data is data :
               return True
           elif self.data > data :
               if self.left is not None :
                   return self.left.Search_BST(data)
               else :
                   return False
           elif self.data < data :
               if self.right is not None :
                   return self.right.Search_BST(data)
               else :
                   return False
           else :
               return False

Yup,You did it,You just learnt implementing BST in python what you thought somewhat hard one with python.Also get the complete source here...
import sys
from collections import defaultdict

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

    def insert(self,data) :
       if data < self.data :
            if self.left is None :
               self.left=Node(data)
            else :
                self.left.insert(data)
       elif data > self.data :
            if self.right is None :
                self.right=Node(data)
            else :
                self.right.insert(data)
                
    def InOrder(self) :
        if self.left is not None :
            self.left.InOrder()
        sys.stdout.write(str(self.data)+" ")
        if not self.right is None :
            self.right.InOrder()

    def PostOrder(self) :
        if self.left is not None :
            self.left.PostOrder()
        if self.right is not None :
            self.right.PostOrder()
        sys.stdout.write(str(self.data)+" ")

    def PreOrder(self) :
        sys.stdout.write(str(self.data)+" ")
        if self.left is not None :
            self.left.PostOrder()
        if self.right is not None :
            self.right.PostOrder()

    def Search_BST(self,data) :
        if self.data is data :
            return True
        elif self.data > data :
            if self.left is not None :
                return self.left.Search_BST(data)
            else :
                return False
        elif self.data < data :
            if self.right is not None :
                return self.right.Search_BST(data)
            else :
                return False
        else :
            return False

print "Building BST..."
for __ in range(input()) :
    if __ is 0 :
        root=Node(input())
    else :
        root.insert(input())
print "Build Completed..."
print "InOrder Traversal.."
root.InOrder()
print
print "PreOrder Traversal..."
root.PreOrder()
print
print "PostOrder Traversal..."
root.PostOrder()
print
print "Searching Starts...\nEnter the no. of elements to search..."
for __ in range(input()) :
    if root.Search_BST(input()) :
        print "YEAH...Data Found"
    else :
        print "OOPS...Data is Not There"
print "Thanks For Reading My Post.Hope you got something Here...!!!"

 I am writing this only to those who feel implementing BST in python is harder.If you are an expert in python, thanks for showing such a great silence in going through this article. If you are the one for whom i'm writing this post, Comment Box is waiting for you...Just go there and post your comments...HAPPY CODING...!!! 

NOTE  : PLEASE GO THROUGH THIS TO GET IDEA AND IMPLEMENT THE SAME ON YOUR OWN.COPY AND PASTE IS EASY BUT NOT WORTHY. IF YOU ARE HAVING TROUBLE IN IMPLEMENTING OTHER BST FUNCTIONS(OTHER THAN THOSE WHICH ARE NOT PUBLISHED HERE)PLEASE COMMENT IT OUT.

y
We