Hi everyone.
In this video let's try to understand what is a binary search tree.
Now, as the name suggests, this is a binary tree.
So every node can have at the most two children.
And this is sorted in a special manner.
Now the values over here for the nodes will be integers.
And it's sorted in this manner such that for every node, the values of the nodes to the left of that
particular node will be less than the value of the node.
So for example, you have a node over here which is ten.
Now if you have a node to its left, this value which is there in this node has to be less than ten.
So for example it can be five.
Now it's also true that the nodes which are to the right of this particular node should have a value
which is greater than the value of the node.
So to the right of this ten I should have some value, which is for example, let's say 20 because 20
is greater than ten.
Now let me just have a point mentioned over here.
In some cases, if there are, the binary search tree allows an equal value to be entered, we would
define that the binary search tree is such that the values to the left are strictly less, and to the
right probably are greater than or equal to.
So again, it depends on how the BST is defined for a particular question.
All right.
Now let's go ahead and take an example.
So over here you have a BST.
You can see that over here the value is 54.
And every value to the left of 54 is less than 54.
And if we go with this definition where we say that the values to the right has to be greater, and
again, it depends on how we define it for any particular question.
So if you get a question on a BST, definitely ask the interviewer whether equal values are allowed
or not.
And what to do if equal values are allowed, typically with equal values will not be allowed, and if
they are allowed, as we have in one of the questions in this section where we deal with the BST construction.
So in that question greater equal values are allowed.
And there we have defined that the value, if it's equal also should be entered to the right.
So again it depends on how we define our BST.
Now over here we have defined that the values to the right has to be greater.
So you can see that these values are greater than 54.
All right.
Now the same holds true for every node.
So for example if you take a look at this.
So over here we have 50.
Now towards its left the value is less than 50.
And towards the right of 50 the value is greater than 50.
And that's also holding true over here.
This is 70 which is greater than 65.
Right.
So whatever is coming over here is greater than 65.
So again it's following the BST property.
Now we have understood what a BST is.
Now.
This is a very important data structure.
Now let's take a quick look at the bigger analysis of common operations for a binary search tree.
Now we have a future video where we discuss this in great detail.
So we are just glancing over it over here.
Now you can see that inserting, searching and deletion for a binary search tree is on average an O
of log n operation.
Now, the intuitive way to understand this is that if you double the number of nodes, the number of
steps will only increase by one.
So we have seen that this pattern over here is represented by log n.
Now let's take an example.
So over here this BST has only three nodes.
And this BST over here has six nodes.
So we have doubled the number of nodes.
Now let's say we want to insert a node with the value 24.
Now if you're doing it in this BST we will do one check where we check the value of 15.
We see that 24 is greater than 15.
So we move in the right direction.
Then we do a second check.
We see that we have 20 over here and 24 is greater than 20.
So we insert it towards the right over here.
So you can see we are doing two operations.
Now.
Over here we have six nodes which is double the number of nodes.
And again if you want to insert 24 in its correct position so that the BST property is fulfilled, we
have to do one check.
We see 15.
We see 24 is greater than 15.
We move in the right direction.
The second check is over here.
We see that 20 and 24 is greater than 20.
We move in the right direction and then we have 25 over here.
And we know 24 is less than 25.
So we move in the left direction and we can insert it over here.
So you can see that we are doing three operations when we double the number of nodes.
And over here we are just doing two operations.
So that's the intuitive way to look at it.
That's why the time complexity is O of log n.
But then we are not covering it in detail over here.
Because again as I said, we are covering it in a future video.
And there the time complexity is analyzed in great detail.
Now why is the worst case O of n?
Let's quickly cover that also.
Now if we have a BST that looks like this.
You can notice that this is actually a valid binary search tree, right?
Everything to the right of ten is greater than ten.
Everything to the right of 12 is greater than 12, everything to the right of 20 is greater than 20,
etc..
So this is a valid binary search tree.
Now over here, if you want to insert something we'll have to go all the way to probably we'll have
to go all the way over here.
Right.
For example, if you wanted to insert 60 now that would be n operations.
So we are traversing the entire binary search tree.
So that's why the worst case is O of n.
Now the solution or the way to avoid this is it's better to pick a different root.
Right over here the root node is ten.
But let's say you pick 20 as the root node.
And in that case the binary search tree would look quite different.
Right.
Let's quickly try to draw that over here.
Now let's say we have 20 as the root node.
So that's 20.
And let's try to insert these nodes.
Let's say we insert 12 and 30.
So 12 is to its left and then 30 is to its right.
Again we can do this in multiple ways.
I'm just doing one way.
And then you have ten over here.
Now ten is less than 12.
So it's over here inserted.
And then we have 50.
50 is greater than 30.
So it's inserted over here.
Now if we want to insert 60 you can see we go from 20 to 30 to 50.
And then we insert it over here.
So you can see that the number of operations has reduced to log n right.