Insertion into BST or Construction of BST in both recursive and iterative approach

Construction of BST is easy than it seems to be 🌻.

We know that, the nodes which are less than the root are present in the left subtree and all the nodes which are greater are present in the right subtree.

all( left )< root < all( right )

Question:

Given an array of unique elements, construct a Binary Search Tree

We will see both iterative and recursive codes in python

Iterative code:

Whenever we create a new Node, we insert its value in that Node and place None as it's left and right

class Node:
    def __init__(self,val):
        self.val=val
        self.left=None
        self.right=None

In the above code, you can see that whenever we initialize the class-Node, we'll be creating a node with value-val, and it's left and right as None

Now we need to create a class that helps us insert a value into it

Let's say there are no nodes inserted into the BST, what would be the root node's value?

• It will be None

So we need to have a function inside the class where when initialized the root=None

class binarysearchtree:
    def __init__(self):
        self.root=None

Now lets talk about insert method

we already know that when a value that is being inserted is lesser than the root, goes to the left subtree and the value is greater then it goes into the right subtree.

                if data>curr.val:
                    if curr.right:
                        curr=curr.right
                    else:
                        curr.right=Node(data)
                        break
                elif data<curr.val:
                    if curr.left:
                        curr=curr.left
                    else:
                        curr.left=Node(data)
                        break

In the above code, we are checking if data(referred to the value we are inserting) is greater than the root's value(curr.val),

• if it is greater, then check if its right is present(i.e if curr.right!=None),

• if it is present we go to the right of it,

• else we check if curr.right==None and then insert the data at that position (i.e to the right of curr) and break the loop.

• It is the same with data<curr.val, except that we'll be going to the left of the subtree.

Did I mention loop, then where is the loop in the above code 🤔,

Here is the whole code for the iterative approach

class Node:
    def __init__(self,val):
        self.val=val
        self.left=None
        self.right=None

class binarysearchtree:
    def __init__(self):
        self.root=None
    def insert(self,data):
        if self.root==None:
            self.root=Node(data)
        else:
            curr=self.root
            while(True):
                if data>curr.val:
                    if curr.right:
                        curr=curr.right
                    else:
                        curr.right=Node(data)
                        break
                elif data<curr.val:
                    if curr.left:
                        curr=curr.left
                    else:
                        curr.left=Node(data)
                        break
ar=[3, 2, 4, 1, 5]
    obj=binarysearchtree()
    for i in ar:
        obj.insert(i)

Now let's go for the mysterious recursive approach

( Background: roaring thunders ⚡ )🤪

recursive approach

The whole logic remains the same, we'll be seeing the difference only in the insert function

def _insert(self,data):
        if self.root==None:
            self.root=Node(data)
        else:
            root1=self.root
            self.insert(root1,data)
def insert(self,root1,data):
        if data>root1.val:
            if root1.right!=None:
                root1=root1.right
                self.insert(root1,data)
            else:
                root1.right=Node(data)
        else:
            if root1.left:
                root1=root1.left
                self.insert(root1,data)
            else:
                root1.left=Node(data)

We are taking 2 insert functions for the purpose of ease of understanding

• When there are no nodes in the BST, we'll just end up at the first insert function( _insert ).

• i.e if we find the root as None, we'll be inserting the first element of the array into the root

• else we are taking a pointer root1 for traversing through the BST, if we consider traversing through the original root itself, then the root may get lost to some other point and the BST will be broken.

• so assigning root1 to root and then passing root1 into insert function

In the insert function

• if data is greater than root1.val we'll be traversing through right subtree,

• and if the right subtree is non-empty then we'll assign root1=root1.right else we'll be inserting the data at that position (self.root=Node(data))

and this follows if data is lesser than root1.val as well.

The whole code is below for the recurssive approach:

class Node:
    def __init__(self,val):
        self.val=val
        self.left=None
        self.right=None

class binarysearchtree:
    def __init__(self):
        self.root=None
    def _insert(self,data):
        if self.root==None:
            self.root=Node(data)
        else:
            root1=self.root
            self.insert(root1,data)
    def insert(self,root1,data):
        if data>root1.val:
            if root1.right!=None:
                root1=root1.right
                self.insert(root1,data)
            else:
                root1.right=Node(data)
        else:
            if root1.left:
                root1=root1.left
                self.insert(root1,data)
            else:
                root1.left=Node(data)
ar=[3, 2, 4, 1, 5]
obj=binarysearchtree()
for i in ar:
        obj._insert(i)

Thanks for reading my first blog post 😄