Hello all and welcome back.
So in this video let us move forward with our discussion on Bsts.
And now let's discuss an operation which you have to perform in a BST.
So the operation is searching in a BST.
Now something similar.
We have of course done in previous generic trees and the binary tree as well.
In a BST let us see how that is going to be different.
So I am just going to explain you, and then I'm pretty sure that you will be able to write the code
for that.
Okay, great.
So in search we will of course be given some value.
Let's say we are given a value okay.
Say 25 okay.
Maybe we can change it.
Now let me take an example.
So let us have an example.
This one which is a little complex and big tree.
So yeah.
Now I have added this particular tree here everyone.
And let us see how are we going to find for 25 in this particular tree.
Great.
Now the way we used to do it in previous trees, that is, the generic and the binary tree where you
used to look at root.
Okay.
Then thinking of your tree in this structure that is consisting of two trees, you used to call both
the sides, right?
So if it is not root then it can be in the left side or it can be in the right side.
That was the understanding the way we used to do.
And we have to go to each and every node.
But we know that binary search tree have a very important and useful property that is on the left of
node.
Everything is smaller and on the right of node everything is bigger.
Now the discussion and the understanding which we had while binary search is going to be a lot helpful
here okay.
So let us see the same everyone.
Let's say you have to find this value in this tree.
You go to root.
You go to root and you first check if root value.
So if the value of your root root dot data is equals to the value.
The best case of course.
Okay, if this is the case, then you can return that.
Yes.
We have find the value return true.
If the root is null, then of course that's the base case.
We will not be doing anything.
We will just simply return false if the tree is empty.
If someone is sending you an empty tree, how will you find any value in that?
Right?
But when we have to call on left and right subtree here, I feel that we can optimize our call.
So let us see.
The same way if I am sure that root data is greater than value okay then do you think we need to find
on this right subtree as well?
Everyone, I don't think that's the case.
The reason is if 40 is bigger than my value, which is 25, everything on the right of 40 will surely
be bigger because that's the property of my BST, and I am given the question that I have to search
in a BST.
One more very thing.
Which one more very important thing which you have to always remember and take care in any question
or in an interview always very clearly read.
If it's a BST question or a binary tree question, or a generic tree question, okay.
Many times you are going to make this mistake where the question will be of binary tree, but you are
going to say you are going to assume a BST and do the same and then waste your time a lot.
So something which I can tell you from experience, never assume that it's a binary tree.
Binary search tree.
Always read the question carefully.
Here I have specifically asked you to search in a BST.
Okay.
So now if the root data is greater, then we can just call search in my left part because I am sure
that it will not be in the right part or right part.
Okay.
So that thing is very important to understand.
Not be in right subtree because it's a BST property.
Now once I come to my left part I see that it is 20.
And now I see that I can just say cliff route dot data.
It's less than my value, right?
So the value is 25.
And I'm saying the route which will basically be the route for the next call, next recursion call.
Right.
The node this particular node it is less.
Now I can be sure that this particular tree can never contain 25.
Same reasoning.
Everything on the left is going to be smaller.
If this is the case, we can just call on right part and then we will see if we are able to find.
But that's the basic understanding which we will be doing.
Okay everyone.
So I hope that is clear.
Let us return maybe true here.
Yeah.
So I guess in that note what's going to happen.
First we will compare with 40.
I will see that it's greater I will go to 21 second.
Yeah.
So I will go to 2020 will say that hey I'm smaller than you.
Go to the right side.
You will not find on the left side.
So the tree is helping you.
30 will say that.
Hey, don't go to my right side.
Just go to my left side and we are able to find the same here.
If it was 26, then we would have made a call here to none, and it would have written false something
which we would have sent back to the old recursive tree.
Right, everyone?
So great.
I hope that is a lot clearer.
And you are able to actually see and experience that.
How this overall thing is helping you in making your operation faster.
Because now we are just making the call to one end or one side of my tree, right?
It's either the right side or the left side.
So just make sure that you quickly code this.
Everyone.
This is the file where you have to write the code.
I can just send a value here as well.
We have this route one, route two and route three.
So you will be having the structure as well.
And I think you should be easily be able to code this particular solution.
Okay.
So great everyone.
Now let's meet in the next video where we will see some other operation on our BST.
Please make sure that you code this.
I am sure that every one of you will be able to do this now.
I have literally explained each and every step.
Okay, so don't skip this please.