In this post, we’ll see how to implement a Binary Search Tree. A tree can be qualified as Binary Search Tree (BST) when it satisfies the following condition :
- Root node is not null
- All the left sub-tree and its children have a value less than or equal to value of root
- All the right sub-tree and its children have a value greater than the value of root
Let’s see the TreeNode implementation in python below :

The implementation of the Tree object is below. The Tree class has the method for all the 3 modes of tree traversal
a)Pre Order Traversal (parsing order root->left subtree —->right subtree )
b)In Order Traversal (parsing order left subtree –> root —> right subtree )
c)Post Order Traversal (parsing order left subtree –> right subtree –> root)
from Node import Node
class Tree:
def __init__(self, rootdata):
self.root = Node(rootdata)
def AddNode(self,root,data):
if data < root.data:
print('to be inserted on left subtree')
if root.left is None:
root.left = Node(data)
print('New node added on left'+str(data))
else:
self.AddNode(root.left,data)
elif data > root.data:
print('to be inserted on right subtree')
if root.right is None:
root.right = Node(data)
print('New node added on right'+str(data))
else:
self.AddNode(root.right,data)
def PreOrderTraversal(self,root):
if root is not None:
print(root.data)
self.PreOrderTraversal(root.left)
self.PreOrderTraversal(root.right)
def InOrderTraversal(self,root):
if root is not None:
self.InOrderTraversal(root.left)
print(root.data)
self.InOrderTraversal(root.right)
def PostOrderTraversal(self,root):
if root is not None:
self.PostOrderTraversal(root.left)
self.PostOrderTraversal(root.right)
print(root.data)
The driver code for running this Tree is below :
When you run this code, you should get the following output.
BnarySearchTree/BinaryTreeDriver.py
to be inserted on left subtree
New node added on left14
to be inserted on right subtree
New node added on right35
to be inserted on left subtree
to be inserted on left subtree
New node added on left10
to be inserted on left subtree
to be inserted on right subtree
New node added on right19
to be inserted on right subtree
to be inserted on left subtree
New node added on left31
to be inserted on right subtree
to be inserted on right subtree
New node added on right42
Output of preorder traversal
27
14
10
19
35
31
42
Output of inorder traversal
10
14
19
27
31
35
42
Output of postorder traversal
10
19
14
31
42
35
You must be logged in to post a comment.