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.