Binary Search Tree Insertion (Iterative method)

Insert into binary search tree.

[zyxwvu]

I think it's more accurate to say that time complexity is o(height of tree). Nice videos, btw!

[sairamsoundararajan]

You sir have helped me understand how to insert a list of integers into a binary tree. thank you for a well-explained video!

[socaexpress]

You have great videos sir ive watched most of them on binary search tree

[Phyniks]

Brother You just helped me understand at the last moment...you are awesome...

[raiyanrazi]

If anyone wants recursive approach, here is the code:

public TreeNode insertIntoBST(TreeNode root, int val) {
if(root==null)
return new TreeNode(val);
if(root.val>val)
root.left = insertIntoBST(root.left, val);
else
root.right = insertIntoBST(root.right, val);
return root;
}

[aniketbhosale]

Hey Tushar Thank you for introducing the basic concepts of BST in these initial videos. Looking ahead for more advance problems for Trees. Thank you :)

[narendrakjha]

Great explanation.

I tried doing it with and without using two pointers.

// Iterative method to insert a new key in BST
public void insertItr(int key) {

Node node = new Node(key);
if (root == null) {
root = node;
return;
}

Node parent = null, current = root;
while (current != null) {
parent = current;
if (key < current.key)
current = current.left;
else if (key > current.key)
current = current.right;
}

if (key < parent.key)
parent.left = node;
else if (key > parent.key)
parent.right = node;

}

// Iterative method to insert a new key in BST
// without using two pointers
public void insertItr2(int key) {

Node node = new Node(key);
if (root == null) {
root = node;
return;
}

Node current = root;
while (true) {
if (key < current.key){
if (current.left == null) {
current.left = node;
break;
}
current = current.left;
}

else if (key > current.key){
if (current.right == null) {
current.right = node;
break;
}
current = current.right;
}
}
}

[ramkumarnarla]

Superb explanation and code. Just handle the case where the given data could already be present in the BST and you're good.

[AdeshPaul]

I have wasted my two hours here and there but at last I found this video very usual. Very nice explanation. Can you please tell me if a node 17 is to be inserted what is the procedure?

[SIKAKOLLUANURAG]

at 4:30, six is not greater than seven!
just pointing out,
great explanation btw!

[paologianfelici]

Hi Tushar, thank you very much for the explanation.

[YogeshDarji]

Awesome explanation Tushar! Just one thing at 4.34, 6 is not greater than 7. Thanks

[ayushsrivastava]

incredible u clear all my doubts.sir can u plz post a program on level order of a binary tree without using queue.

[siddhi_chotaliya]

you are excellent but i think(for me) you are bit fast to explain your solutions..
i keep repeating you one video and then i understand it.
but still u expand it well.

[saurav]

Hi Sir,
i think the function should be of return type Node* (not Node) and the parameter to the function insert should be a pointer to Node i.e Node* root. so right function should be like this

Node* insert(Node* root, int data)
{
Node* node=new Node();



}

[mohitsingh-nfvl]

Node * should be the function type as return type (root) is pointer

[pawankumarjajara]

Tushar: Can't we drop parent Object? current is going to point to leaf node when while loop breaks out. No?

Good explanation!

[surojitkarmakar]

sir please give us....binary search tree's deletion video.... it's my humble request...sir..🙏🙏🙏🙏🙏

[arjunraj]

instead of using two pointers current & parent, cant we manage with a single pointer??

[AmandeepSingh-fcfv]

Hi Tushar, Can you please clarify how "return root" statement return back the whole tree ?