A Binary Search Tree (BST) is a tree in which all the nodes follow mentioned properties :

• The left sub-tree of a node has a key less than or equal to its parent node’s key.
• The right sub-tree of a node has a key greater than to its parent node’s key.

Lets create or insert these nodes using programming:

Creation or Insertion of BST with Python:

Step-1: Create Node Class : Intially Node left and right child are none and constructor take node value as an argument.

class Node:
# Define the Constructor
def __init__(self,key):
self.left = None
self.right = None
self.val = key 

Step-2: Create BST Class : It contains insert_bst method, take two arguments-root and node, that is the object of Node class defined in Step1.

root.val,node.val,root.left,root.right are the Node object fields defined in Step1.

class BST:

#Insert the Node object(defined in Step 1) into tree
def insert_bst(self,root,node):
if root is None:
root = node
else:
if root.val < node.val:
if root.right is None:
root.right = node
else:
self.insert_bst(root.right, node)
else:
if root.left is None:
root.left = node
else:
self.insert_bst(root.left, node)


Step-3: How do we know that Binary search tree formed or not? Lets print the node values using Inorder Tree Traversal method. It consist inorder_bst method that take the Node class object defined in Step-1 as an argument.

 def inorder_bst(self,root):
if root:
self.inorder_bst(root.left)
print(root.val)
self.inorder_bst(root.right)


Lets combine Step-1,Step 2 and Step-3 steps and run it.

class Node:

# Define the Constructor
def __init__(self,key):
self.left = None
self.right = None
self.val = key

class BST:

#Insert the Node object(defined in Step 1) into tree.
def insert_bst(self,root,node):

if root is None:
root = node
else:
if root.val < node.val:
if root.right is None:
root.right = node
else:
self.insert_bst(root.right, node)
else:
if root.left is None:
root.left = node
else:
self.insert_bst(root.left, node)

#print the node using Inorder Traversal
def inorder_bst(self,root):

if root:
self.inorder_bst(root.left)
print(root.val)
self.inorder_bst(root.right)



#Create the object of Node class
rtn = Node(100)

#Create the object of BST class
obj_bst=BST()
obj_bst.insert_bst(rtn,Node(80))
obj_bst.insert_bst(rtn,Node(70))
obj_bst.insert_bst(rtn,Node(90))
obj_bst.insert_bst(rtn,Node(110))
obj_bst.insert_bst(rtn,Node(120))
obj_bst.insert_bst(rtn,Node(105))

obj_bst.inorder_bst(rtn)

Output:

Inorder traversal of BST always produces sorted output.

The worst case time complexity of search and insert operations is O(h) where h is height of Binary Search Tree.

Hopefully you understand the creation of BST. Please do comment in case of any questions and share it further if you liked it.

Happy Learning 🙂

Categories: Miscellaneous

$${}$$