Insertion in Binary Search Tree(BST) in Python

Basic Operations on Binary Search Tree (BST)

Searching in Binary Search Tree in Python

Inserting a node in a Binary search tree involves adding a new node to the tree while maintaining the binary search tree (BST) property. So we need to traverse through all the nodes till we find a leaf node and insert the node as the left or right child based on the value of that leaf node. So the three conditions that we need to check at the leaf node are listed below:

Illustrations

Let us insert 13 into the below Binary search tree

Binary Search Tree

When we call the insert method then 13 is checked with the root node which is 15 , Since 13 < 15 we need to insert 13 to the left sub tree. So we recursively call left_sub_tree.insert(13)
Now the left child of 15 is 10 so 13 is checked with 10 and since 13>10 we need to insert 13 to the right sub tree. So we recursively call right_sub_tree.insert(13)
Here, the right child of 10 is 11 so 13 is checked with 11 and since 13>11 and we need to insert 13 to the right child of 11. Again we recursively call right_sub_tree.insert(13)
In this recursion call, we found there is no node which means we reached till the leaf node, so we create a node and insert the data in the node
After inserting 13 , the BST looks like this :

Inserted 13 Node in Binary Search Tree

Insertion in Binary Search Tree (BST) in Python

Python3

class Tree:
    def __init__(self,val=None):
      
        # Initialize the Tree node with a value
        self.value = val
        
        # If the node has a value, 
        #create left and right children nodes
        if self.value:
            self.left = Tree()
            self.right = Tree()
        else:
          
            # If the node has no value, 
            #set left and right children to None
            self.left = None
            self.right = None
    
    # Check if the node is empty (has no value)
    def isempty(self):
        return (self.value == None)
    
    # Insert a new value into the tree
    def insert(self,data):
      
        # If the node is empty, insert the data here
        if self.isempty():
            self.value = data
            
            # Create left and right children 
            #for the inserted node
            self.left = Tree()
            self.right = Tree()
            print("{} is inserted successfully".format(self.value))
            
        # If data is less than current node value, 
        #insert into left subtree
        elif data < self.value:
            self.left.insert(data)
            return
          
        # If data is greater than current node value, 
        #insert into right subtree
        elif data > self.value:
            self.right.insert(data)
            
        # If data is equal to current node value, do nothing
        elif data == self.value:
            return

# Create a tree with root value 15
t = Tree(15)
# Insert some values into the tree
t.insert(10)
t.insert(18)
t.insert(4)
t.insert(11)
t.insert(16)
t.insert(20)
t.insert(13)

Output

10 is inserted successfully
18 is inserted successfully
4 is inserted successfully
11 is inserted successfully
16 is inserted successfully
20 is inserted successfully
13 is inserted successfully

Time complexity: O(log n)
Space complexity: O(n)

Binary Search Tree In Python

A Binary search tree is a binary tree where the values of the left sub-tree are less than the root node and the values of the right sub-tree are greater than the value of the root node. In this article, we will discuss the binary search tree in Python.

Insertion in Binary Search Tree(BST) in Python

Illustrations

Binary Search Tree In Python

Similar Reads

Contact Us