Insertion Operation in BST

Insertion in BST

To insert a new node into a Binary Search Tree (BST), you can follow these steps:

Example

Using the given root value of 50, let's insert the keys 80, 30, 20, 100, and 40 into the Binary Search Tree (BST):


Initial BST:

     50


Step 1 :- Inserting 80:

     50

      \

       80

Inserting 80: Since 80 is greater than 50, it is inserted as the right child of the root node.


Step 2 :-Inserting 30:

     50

    /  \

   30   80

Inserting 30: Since 30 is less than 50, it is inserted as the left child of the root node.


Step 3 :-Inserting 20:

     50

    /  \

   30   80

  /

 20

Inserting 20: Again, 20 is less than 50, so it is inserted as the left child of the node with key 30.


Step 4  :-Inserting 100:

     50

    /  \

   30   80

  /    /

 20   100

Inserting 100: Since 100 is greater than 50, it is inserted as the right child of the root node.


Step 5 :-Inserting 40:

     50

    /  \

   30   80

  /    / \

 20   40  100

Inserting 40: Since 40 is greater than 30 but less than 50, it is inserted as the right child of the node with key 30.


Code Snippet

Here's a Python code snippet that demonstrates the insertion operation in a BST:

class Node:

    def __init__(self, key):

        self.key = key

        self.left = None

        self.right = None


def insert(root, key):

    if root is None:

        return Node(key)  # Create a new node if the tree is empty


    if key < root.key:

        root.left = insert(root.left, key)  # Recursively insert into the left subtree

    elif key > root.key:

        root.right = insert(root.right, key)  # Recursively insert into the right subtree

    return root


# Example usage

root = None

root = insert(root, 50)

root = insert(root, 80)

root = insert(root, 30)

root = insert(root, 20)

root = insert(root, 100)

root = insert(root, 40)


In the above example, the insert function takes the root of the BST and the key to be inserted. It recursively finds the appropriate position for the new key in the tree based on the comparisons and creates a new node with the key. The updated root is returned after the insertion is complete.