Insertion in Binary Search Tree with Python

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 🙂