Hello all and welcome back.
In this video we want to now implement the Binary Search tree class.
Okay, so many of you might be thinking that why haven't we implemented the same for previous generic
trees or binary trees.
We have studied those kind of tree as well, right?
Well, the reason for that is let's say you are given a normal binary tree.
Okay.
So it is 50 here and let's say it is some five.
And if I ask you to now add say 20 to it okay.
Let's say I'm asking that hey add 20.
Do you think like it's doable.
Like there is some default way you can do that.
Like I see that there are four positions where this can be added, right?
So it doesn't actually make any sense that you will be creating an insert function.
And then you will be saying that, hey, can you insert this particular node into your tree?
And I don't have any logic defined similarly for deleting any node okay or overall for any other operation.
We anyway have to go to each and every node, right?
But for the binary search tree we have the property which we can use.
So let me write that down as well.
For binary tree.
And generic trees.
No logic is defined right.
So no major logic is defined because of which we need to make sure that for BST we are able to add it.
And actually I can help you visualize the same as well.
Like always, I have this visualizer for you in this what we are trying to do.
Let's say you add ten as a node okay.
So I'm saying insert ten is inserted.
Now let's say I want to add 20 and I click insert.
20 is added here right.
Now say I want to add five.
Now you will also be able to think that hey where this five should be added.
Right.
So five is added here.
Now let's say I add nine insert.
So this overall structure right.
It has a meaning to it.
It has some property which it is trying to follow.
And we have to do the same thing okay.
So there are going to be three major functions which we have to implement.
So three major functions are actually there three major functions or methods.
We can say okay they will be methods only.
So let us keep that in line.
They will be methods right.
First is going to be insert.
Second is going to be search.
And third is going to be delete.
Now we can have the traversal as well with respect to post-order preorder in order, but I'm pretty
sure that you all will be able to do that.
These are the three major functions which we have to perform on our BST class.
Okay.
So when a person says insert, you will have to always make sure that we are maintaining that it should
remain.
A BST is BST will not be a function.
The reason for that is we are taking the onus that hey, I will be maintaining this as a BST.
Okay.
No matter what operation you do, if you are inserting anything, if you are deleting anything, I will
be making sure that at the back end the whole thing is saved as a BST.
Okay.
So that's the overall idea everyone.
Now let us move forward and discuss a little bit on this.
Right.
And you will see that these were the three methods which were there on the visualizer as well.
Right.
So let me go to the visualization in the visualization if we see here search insert and remove.
Right.
So if let's say I search for nine, it will tell that nine is in the tree.
Right.
These inorder preorder everything.
I'm pretty sure you will be good to.
Right.
So in order it is giving us right.
Great.
So now let us move forward and see how will we overall implement this particular class.
Right.
So first I have to create a binary tree node or binary tree search node.
You can create it anyways okay so let us create it BST node only.
Let us keep it as direct BST node.
So this we have written lots of time def init self and you will be giving me some data now.
Self dot data equals data.
Self dot.
Left.
Self dot.
Left will be none.
And similarly self dot right is none as well.
Right.
So this is our best node.
Normal.
Now what I have to do.
Class best.
Okay so this is the major class which I have to implement wherein I will be giving you these functions.
Okay.
Great.
Methods dot function.
First is constructor.
So let's see if what is exactly the constructor here.
Right.
Let's go back to the visualization.
If I just refresh it what are we seeing.
We are seeing that it's an empty tree right now.
This is the overall condition which should be there in my constructor.
Right.
So I think we have seen this a lot of time.
We can say self dot route is none.
So as of now, it is empty.
Okay, great.
Now we want these functions.
Insert will, you will be giving me some data.
So we want these methods search again.
You will be giving me self or self.
Sorry I will have.
And you will be giving some data which I have to search and finally delete where again you will be giving
the data.
Okay.
So this these are the three functions or sorry methods which I have to implement.
Right?
I think search one is something which we have done already.
Search is some method which we have done previously.
So this is where I asked you to implement the search.
And we discussed the same in length okay.
So overall you would have completed this.
But there is some caveat which I would like to discuss.
Okay.
So let us first complete search.
So pay attention everyone.
What's going to happen in search.
And let me just copy it down here so that we can complete it.
Great.
So when I'm doing for search, let us pick up search as the first one because that is something we have
already done.
If I ask you to search for a particular node in my BST, what exactly do we have to do?
Let me do it again and nicely.
Yeah.
We have to go through nodes.
Okay.
Based on some condition.
And then say if I'm able to find that particular node or not.
Right.
So it is based on checking the value with and comparing that with the root.
And we used to call one half right.
We used to call on either the left half or the right half.
Right.
So that is something which we used to do when we used to search for our best.
So let us write the code for that.
Uh, first thing is if root is none.
Okay.
So we are taking self, uh, I will have to take self dot root.
Okay.
So self dot root.
If it is none then I can just return none or false.
Okay.
So I am returning false.
Great.
If root dot again self dot root dot data equals to data.
Okay.
So I hope till now we have this habit that we know this data is different.
It is present inside my root.
And this data overall is different right.
If this is the case we will return true.
Right.
If it is not like if the root is not equal to data, then what we used to do, we used to use recursion
to my recursion.
After comparing, I used to either call on the left or I used to call on the right.
So in this case, what can I do?
Everyone pay attention here.
Now I am saying that hey, I can either call to the left or to the right, so let us do that.
If data is less than root dot data okay.
And self dot root.
Self dot root dot data.
Then I have to call to return search.
In this I think I should call to the left right because the data is less than the root.
It will be available in the left subtree.
If the root is 50, then everything smaller than 50 is to the left of my tree.
Now let's let me call this search.
Okay.
So I can pass the data.
That is fine.
How should I pass this?
Overall it is Yeah.
How should I pass this?
So self dot search.
Okay.
In this particular code, how can I say that?
Hey, look only in the right part, or look only in the left part, because we are asking just for the
data from the user, right?
My user will not say that.
Hey, look, start from root for the end user.
He will just be imagining a tree.
So I hope you are able to understand.
Let me just explain.
It's ten.
Let's say 20.
Let's say zero.
Let's say five for let's say 12.
Okay.
Now when I ask to search for a particular value, I don't say that.
Hey, look at the root or start from the root.
I mean the whole tree, right?
So when user will be making an object based object, let's say it is BST class okay.
He will be calling this search function with just the data which you want.
Let's say he wants to find ten.
Now, I cannot assume or ask the user that hey, please send maybe BST object.
Dot root.
He will not be doing that right.
That is something which I have to handle.
So if the problem is clear then I think you must be till now able to search like get the solution as
well.
Solution is that I will create a helper because I cannot change.
I cannot ask my user that hey, you give me the overall root, the left or right.
So I'm going to create a helper in this helper.
So let's say self dot search helper.
I will be passing the data as it is and I will pass the root.
And I can take root here.
Okay.
And now I should work on this route instead of self.
Because if I don't do this, then I will be keeping on working on self dot route, which is the topmost
element of my tree.
So I will keep on working on this ten only.
Okay, if I don't do this kind of a change and define a helper function, self dot route will always
have a value of ten.
And now we can say that hey, now using this helper function, it is analogous to what we wrote.
Great.
So instead of search it will be search helper here.
And I can send route dot left.
Similarly if it is not there else return.
Route dot right.
Okay, so just a small caveat was there that we don't want our user to send me the route.
We want to use it, but then also we want to use recursion.
So I have to write a method or a helper method which takes in the overall things in this respect.
Okay.
So that was basically the idea.
We can make it private as well.
But I think for the time being it is not a problem.
So this is how search will happen.
Okay everyone.
Now let's move to insert.
So talking about insert, this is something which you all are going to implement.
Let's talk that okay.
How exactly are we going to insert first.
Okay great.
Let's say I have to insert key which is say m nine okay.
I have to insert nine.
How exactly is the process going to go.
I believe we will see if our what our root value is.
Okay.
Let me make it blue color Based on a root value.
If the value which I want to insert in this example line, if it is greater, then I will ask it to
get inserted in my right subtree.
If it is smaller then it should be inserted in my left subtree.
Right.
So in this case it is smaller.
So I will call on my left subtree.
It will go here.
It is going to call on my right subtree.
It is going to call on my right subtree because nine is greater than zero right.
Similarly for four it is going to call on my right subtree.
Now when I reach here when it is none, then actually we can insert it because normally as well, if
I just, uh, make a copy of this tab.
So one second, let me duplicate this tab.
And when I normally say that hey insert ten okay.
Or insert nine.
If the root is none, then it directly inserts that, right?
So what is going to happen?
It is going to insert and return back the new root or this particular node which we have to connect.
Okay everyone.
So I hope you are able to understand what exactly we have to do here.
We just have to make sure that if the data is less, we ask the left subtree to handle that.
If it is more, we ask the right subtree to handle that.
Okay, straightforward.
It's all almost on the similar line of search, just that this time we will not return true or false.
We are going to ask recursion and a node will be created at the right position okay.
So I want all of you to just try to implement it once.
And in the next video we will see the solution and also how to handle the use case of delete.
Okay so great everyone do give it a try and we will meet in the next video where we will see how insert
can be done.
And if delete is also that simple.
Okay.