##  ### Binary Search Tree in Python

 ```''' Binary Search Tree is a binary tree(that is every node has two branches), in which the values contained in the left subtree is always less than the root of that subtree, and the values contained in the right subtree is always greater than the value of the root of the right subtree. For more information about binary search trees, refer to : http://en.wikipedia.org/wiki/Binary_search_tree ''' #Only for use in Python 2.6.0a2 and later from __future__ import print_function class Node: # Constructor to initialize data # If data is not given by user,its taken as None def __init__(self, data=None, left=None, right=None): self.data = data self.left = left self.right = right # __str__ returns string equivalent of Object def __str__(self): return "Node[Data = %s]" % (self.data,) class BinarySearchTree: def __init__(self): self.root = None '''     While inserting values in a binary search tree, we first check     whether the value is greater than, lesser than or equal to the     root of the tree.     We initialize current node as the root.     If the value is greater than the current node value, then we know that     its right location will be in the right subtree. So we make the current     element as the right node.          If the value is lesser than the current node value, then we know that     its right location will be in the left subtree. So we make the current     element as the left node.     If the value is equal to the current node value, then we know that the     value is already contained in the tree and doesn't need to be reinserted.     So we break from the loop.     ''' def insert(self, val): if (self.root == None): self.root = Node(val) else: current = self.root while 1: if (current.data > val): if (current.left == None): current.left = Node(val) break else: current = current.left elif (current.data < val): if (current.right == None): current.right = Node(val) break else: current = current.right else: break '''     In preorder traversal, we first print the current element, then     move on to the left subtree and finally to the right subree.     ''' def preorder(self, node): if (node == None): return else: print(node.data, end=" ") self.preorder(node.left) self.preorder(node.right) '''     In inorder traversal, we first move to the left subtree, then print     the current element and finally move to the right subtree.     ''' #Important : Inorder traversal returns the elements in sorted form. def inorder(self, node): if (node == None): return else: self.inorder(node.left) print(node.data, end=" ") self.inorder(node.right) '''     In postorder traversal, we first move to the left subtree, then to the     right subtree and finally print the current element.     ''' def postorder(self, node): if (node == None): return else: self.postorder(node.left) self.postorder(node.right) print(node.data, end=" ") tree = BinarySearchTree() tree.insert(1) tree.insert(9) tree.insert(4) tree.insert(3) tree.insert(5) tree.insert(7) tree.insert(10) tree.insert(0) print ("Preorder Printing") tree.preorder(tree.root) print("\n\nInorder Printing") tree.inorder(tree.root) print("\n\nPostOrder Printing") tree.postorder(tree.root) ```
 Source code: Chars: 3837