Hi everyone.
Let's do this question.
Design a binary search tree class that supports the following.
Insert a value.
Remove a value.
This method should remove the first occurrence of a value and then find a value.
If the value is found, it should return the node with the value.
Else return false.
Now, because this is a standard question, let's directly dive in and see how we can solve this question.
So we have to design a binary search tree.
And these are the three functions that we should write.
All right so insert remove and find.
So these are the three functions that we should write.
Now let's get started with the insert function.
Now for this let me just take a sample binary search tree over here.
Now again when the initially the binary search tree is empty.
And let's say we insert 20.
So at that point we have to set 20 as the root node.
All right.
Now after that let's say all these nodes are already inserted so that we take a generic case and we
can understand how the insert function works.
So over here we have a binary search tree.
You can notice that every element or every node to the left of 20 is less than 20.
And every node to the right of 20 is greater than 20.
Right.
So that's the binary search tree property.
Now let's say we want to insert a node with value 29.
So what do we do.
So over here we start always at the root.
All right.
So we start at the root.
So we start at 20.
And we compare the value at this node with the value to be inserted.
So we see that 29 which is the value to be inserted is greater than 20.
Right.
So in this case what we do is we move to the right.
So we move to the right in the binary search tree.
Now we check whether over here is there a node or is it null if over here there was nothing and if there
was just null over here, we could have just inserted 29 over here.
But now we see that there is another node over here which is 35.
So we compare the value of this node and the value of the node to be inserted.
So we see that 29 is less than 35.
Right.
So because it's less we move in the left direction.
So again we move over here and we check whether over here is there a node or is it null.
So if it was null over here we would have inserted 29 over here.
But we see that there is a node over here.
So we compare 27 and 29.
And we see that 29 is greater than 27.
So we move in the right direction.
But over here we can see that there is nothing over here.
Right.
So the right node to 27 over here is null.
So we can just insert 29 over here.
And that's how the insert function will work.
Right.
So it's pretty straightforward.
We just need to be aware how to traverse the tree.
So if we find a value if we see that this value over here is less than 29 for example, what we saw
over here, we move in the right direction, right.
So over here we have something which is greater than 2920 right.
So we move in the right direction.
And over here again we saw that 29 is less than 35.
So we move in the left direction.
So that's it.
And then we do this till we reach a place where nothing is there.
And then we insert 29 in the correct place.
All right.
So that's how the insert function works.
Now let's look at the find function which we have to write.
And again it's also similar.
We just need to traverse the tree and look at the correct position right.
For example let's say we want to see whether there is a node with value eight.
So again we start at the root node which is 20.
And we compare 20 with the value eight.
And we see that eight is less than 20.
And we know that any node which has a value less than 20 has to be part of the left subtree.
Right.
So we started the node and as eight is less than 20 we move in the left direction.
Now we have six over here again we compare six and 20.
And we see that six is less than eight right.
Again not six and 26 and eight right.
So eight is the value that we are trying to find.
So we see that six is less than eight right.
So eight which is greater than six has to be on the right side of six.
Right.
Because anything greater than six has to be on its right side.
So we move in the right direction and over there again we come to eight and we see that yes eight is
equal to eight.
So we have found the node.
Now let's say there was uh another node over here.
Let's say for example we are trying to find the node with value nine.
Again we would have taken the same direction.
We would have started at 20.
And then we come to six.
Then we move in the right direction and we come to eight.
And then because we want to find the node with value nine, it has to be there on the right side of
eight, if at all it is there.
Right.
So we check is there anything over here.
And let's say we see there is nothing.
It's null right.
So at this point we can be sure that there is no value nine in this binary search tree.
All right.
So that's how the find function works.
So we have seen the insert function and the find function.
Now let's proceed and look at the remove function.
So these two are very straightforward.
The insert and find function.
Now in the remove function let's see the different cases which are possible.
Again we have our simple binary search tree over here.
Now the no.
Which is to be deleted, right?
Can be of three possible types one.
It could be a leaf node.
Second, it could be a node which has only one child.
And third, it could be a node which has two children.
So these are the three possibilities right now let's see how to tackle these possibilities.
Now let's say it's a leaf node.
So let's say we just want to remove a node which is a leaf node.
For example let's say we want to delete the node with value 25.
And you can see that it's a leaf node.
So first we have to find that node right.
So that's the first step.
And we have already discussed how we can do that.
Right.
So we start at 20 and then we move in the right direction because 25 is greater than 20.
Then we reach 35.
We move in the left direction because 25 is less than 35.
And then we reach 27.
And again we move in the left direction because 25 is less than 27.
So we have found the node which is to be deleted because 25 is equal to 25.
Now at this point, because this is a leaf node, all we need to do is just we need to replace this
with null.
Right.
So there's there's nothing else to be done.
Now replacing this with null means the parent.
This is the parent right of 25.
We have to say this node the parent let me just call it p.
So this is the parent.
We have to say parent dot left is equal to null in this case.
So in this way we have replaced this node with null.
And that's deleting a leaf node.
So we are done with this case over here.
Now let's proceed to the second case.
And let's say we want to delete a node which has only one child.
For example let's say we want to delete 55.
All right.
So let me just clear this up a bit.
Now the first step is again to find the node which is to be deleted.
Right.
So we have to find this node which is similar to what we discussed over here and in the first case as
well.
So once we have found this node now we need to know that this is a left child.
Right.
So this is a left child of this parent.
So we have to say oh sorry this is a right child right.
So this is a right child.
Let me just write this over here.
This is a right child.
So we have to say parent dot right.
Right.
Parent dot right is equal to 60.
So that's how we delete this node right.
So parent dot right has to be equal to 60.
All right.
So this is again a right child.
So parent dot right is equal to 60.
And that's how we delete this.
So these two cases are pretty straightforward right.
If it's a leaf node we have to just set it to null.
And in this case what we did is parent dot left is equal to null.
So that's how we made this null.
Now if it has only one child we have to say parent dot right or dot left depending whether the node
to be deleted is a left child or a right child.
And then we have to set that to the child of this particular node.
And again remember it has only one child.
So if it has a right child then we say parent dot right is the right child.
And let's say it had only a left child, like for example, this was not there.
And let's say it just had a node 54 over here in this case also because this is over here, a right
child, we have to say parent dot right is equal to this 54 over here, which is equivalent to making
this connection.
All right.
So we have discussed how to tackle these two cases which is deleting a leaf node and deleting a node
which has only one child.
Now let's proceed to the third case which is deleting a node which has two children.
Now for example let's say we want to delete the node 20.
Now over here 20 is a node which has two children, right?
Six and 35.
Now the first step is again finding the node.
Right now we start at the root node.
And because over here 20 is the root node itself we have found the node.
Now if it was not the case let's say we wanted to delete 35.
The same procedure follows.
We have to start at 20.
Move to the right.
And then we find the node which has to be deleted.
All right.
Now once we have found the node which is to be deleted.
The next step is to replace that particular node, which is to be deleted with its in-order predecessor
or successor.
Now, what do I mean with this?
Now, in the next question, we will deal with in-order traversal depth.
First search of in-order type of a binary search tree.
So there is a different question for that.
So you can go and refer that.
Now when we you will see it over there that when you do in-order traversal on a binary search tree,
you will get the elements in ascending order.
Right.
So let's just write 20 over here and what would be its previous number, let's say over all the elements
over here are written in ascending order, that is, from the smallest to the largest.
Now if we just do that, you can see that you will have eight and then you will have 20, and then you
will have 25.
Right.
And then it will go on like that.
Right.
So again just refer the video where we discuss in-order traversal of a binary search tree.
And there you can see that.
So when you do that you will get the elements in ascending order right.
So over here also let's just write it out.
If you do, if you arrange all these elements in ascending order, how would it look like.
So we have one.
Then we have three.
We have three, then we have six, then we have eight, then we have 20, then we have 25.
Right.
So it goes on like that.
Then we have 27.
Then you have 29, then you have 35, 55 and 60.
So this is the ascending order.
So if you were to do in-order traversal of the binary search tree, you and then you print all the elements
into an array.
For example, you store all the elements in an array and you just um, print that array.
So then it would look like this.
All right.
So over here we have 20 which is the node to be deleted.
So now what we need to do is we found the node.
And now we need to replace it with its in-order predecessor or successor.
So the predecessor of 20 is eight over here.
And the successor of 20 is 25.
All right.
So again just repeating what we have to do.
The first step is finding the node to be deleted.
And the second step is replacing it with its in-order predecessor or successor.
Now let me just clear this up and let's see how we do this.
So I just wanted to mention this over here because you will see this in different sources.
Right.
So I just wanted you to be aware what is the in-order predecessor and successor.
And again, it's just a technicality right now.
Let's see how we proceed with this.
Now, the in-order successor or the next greatest value after the node which is to be deleted, will
be the smallest node in the right subtree.
So this is the right subtree of 20, right.
So this is the right side of 20 right.
So if you take the smallest value of this you will get 25.
So that will be the in-order successor of the node to be deleted.
Now what about the predecessor.
The predecessor would be the largest value in the left subtree.
You can see that the largest value over here is eight right.
So you can proceed in either way.
So you can either replace 20 with eight.
So if you do that let's say for example you write eight over here and you remove this, you can see
that this follows the binary search tree property.
Right.
Everything on its left is less than eight and everything on its right is greater than eight.
So that's why we are actually taking one of these two elements and putting it on the on the node, which
is to be deleted, right?
So that the property is maintained.
You can see if you put eight over here, everything on its left is still less than eight and everything
on its right is still greater than eight.
Now you could also replace this 20 with this 25, which is the smallest element in the right subtree.
So let's say we put 25 over here.
If you put 25 over here, you can see everything on its left is less than 25 and everything on its right
is greater than 25.
Right now, everything on its right will be greater than 25, because this is the smallest element in
the right subtree.
So that's the logic behind this.
Now let's go ahead and take one of these approaches.
Right.
You can go with either approach.
Now in this video we will go with the approach where we find the smallest element in the right subtree.
So that's the approach we are going to take.
All right.
So this is the right subtree.
And we are trying to find the smallest element in this right subtree.
And you will notice that the smallest element in this right subtree will be the left most element right.
Why is that so?
Because whenever we have something which is less than the node right, we always move in the left direction,
right?
So for example let's say you wanted to insert 25.
So you started and let's say 35 is the node right.
So this is let's consider this as a subtree.
So the node of this subtree let's say it's 35 right.
So 25 is less than 35.
So you move in the left direction.
Now 25 is less than 27.
Again you move in the left direction right.
So we just need to find the left most element to find the smallest element.
Now in the same manner, if you were to find the largest element in this left subtree, you you should
have found the right most element right.
So.
The right most element will be the largest element.
All right.
So that was just a sub point.
So let's proceed and see how we can find the left most element.
And then what should we do.
So again, let's say we have this node.
We know that we need to find the left most element in this subtree.
So we just keep moving left as long as we can.
Right now if we move left after this we get to null right.
So the left of this node over here is null.
So then we know that we have found the left most element and that will be the smallest element.
Now what we need to do is we need to take this value.
And we replace and put that value on the node which is to be deleted.
So we wanted to delete this 20 node.
Right.
So we take we find this left most element and we put this value over here.
All right.
Now what we need to do is we need to change this to null.
And we are done.
Right.
So that's all.
So we just need to find the left most element and then put that value over here.
And then we need to change this to null.
So how do we do this again.
For this we will have a function.
And we will recursively call that function on this subtree with the new value.
All right.
So initially we call the remove function on the whole binary search tree.
And we pass in the value 20.
So that finds 20.
Then we will have a function which will find the minimum value from the right subtree.
We get that value back and we put it over here which is on the node which is to be deleted.
Then we again call the remove function on the right subtree and we pass the value 25 at this time,
initially, the value 20 was passed because we wanted to delete that right now in this right subtree,
we just want to delete the value with the node with value 25, because we don't want to duplicate it.
Right.
So we again recursively call the remove function.
But at this point the space complexity will not improve, will not increase.
Because you can see that we are just calling it two times.
It's not we are not implementing a recursive solution.
Over here we are discussing an iterative solution, but we have a recursive call which is happening
only one time.
So we call it on the right subtree to delete this node.
All right.
Now there is also one more possibility.
Let's say this node 25 over here had a right child, which is 26.
What would have happened in this case?
In this case also the leftmost element is still 25, right.
So we find 25 and we put the value of 25 on the node which is to be deleted, which is 20 over here.
And then we say that 27 dot left is 26 or its child.
Right.
So 27 dot left is 26 which is the child of it.
So again that's similar to deleting a node with one child, which is something that we have already
discussed.
So this is how we handle deleting a node which has two children.
All right.
Now again remember to do this operation over here.
That is either to set 20.
This node over here to null and 27 dot left will be null.
Or if it had a child 27 dot left will be this 26 over here.
And again there will not be a case where you have a child, a left child for 25, right?
Because in that case that would be the left most element.
All right.
So over here we just set 27 dot left is 26.
Now to do this we recursively call the remove function one more time.
All right.
So that's how we do the remove function.
And we have discussed the three possibilities.
The possibility where the node to be deleted is a leaf node.
The possibility where it's a node with only one child.
And the third possibility where the node to be deleted is a node which has two children.
So in this case, we find the smallest element in the right subtree.
We put that value on the node which is to be deleted.
And then we just remove that node from the right subtree.
All right.
Now let's quickly look at the complexity analysis of this solution which we discussed.
Now the time complexity for insert, remove and find will be O of log n best and average case, and
it will be O of n in the worst case.
Now let's try to understand this.
Now over here for inserting or removing or finding the number of operations is happening because we
need to find it, right.
We need to find the node which is to be in the the correct place for inserting the node or the node
which is to be removed, or searching for the node.
Right.
So we need to do a set of comparisons to reach to the correct place.
So the number of comparisons will be equal to log n in the case that the tree is balanced.
Right.
So that's why we say that the time complexity is O of log n in the best and average case.
So it's nothing but the height of the tree, right.
In the case it's a balanced tree.
Now why do we say that it's not always O of log n because there is a possibility like this, right.
If you have let's say a binary search tree like this.
Now this looks like a linked list, but in fact this is a valid binary search tree.
Let's say you inserted one, then you insert two.
So two is greater than one.
So you insert it on its right right.
Then again you insert a node with value three.
So that is also greater than two.
So it goes to the right of two.
And then you insert a node with value four.
So that also goes to the right of three.
So this is a valid binary search tree.
But it looks like a linked list right.
And that's why.
I.
If you want to insert something, we would have to go in all this way, right?
Let's say you want to insert five.
You have to do n number of comparisons and insert five over here.
So that's why we say that the worst case time complexity is O of n.
In the case of a binary search tree for insert, remove and find.
All right.
Now how do we solve this.
The best way to solve this is don't take one as a root.
Let's say for example you take two as root.
Now the binary search tree would look like this.
Right now in this case, the number of comparisons you have to do is just log n which is log four.
In this case because you have four roots right?
Four nodes.
So the number of maximum number of comparisons you have to do is just log four which is equal to two.
Now also notice over here log n is the minimum possible height right.
So that's why we say it's the best case.
Also this is the minimum possible height right.
If you have n nodes.
And if you are making a binary search tree.
So the minimum possible height is log n.
Now you can have a greater height like for example over here right 1234.
So over here the height is not two right.
But in this case the height is two.
So the minimum height is also log n.
All right.
Now let's also look at the space complexity.
We have seen that the time complexity is O of log n best and average and O of n in the worst case.
Now what about the space complexity.
Now the space complexity will depend on the approach you take to implement these functions the insert,
remove and find functions.
Now you can implement this insert, remove and find function in two ways.
If you do it recursively, then the space complexity will be O of log n average and worst case.
Now in the worst case you will have n calls on the call stack.
Right now, in the average and best case you will have log n calls.
So that's why we say that the space complexity is O of log n average and best case and O of n worst
case.
Now if you do it iteratively like we have discussed, and in this video and in this code section, we
will be implementing this in the iterative manner.
And you will see that this has a better space complexity, which is O of one, because we are not going
to have uh n or log n calls on the call stack.
Now also notice over here one extra call is there on the call stack.
But again O of two is nothing but O of one itself, right?
If you say that it's O of two.
The space complexity, this is just a constant.
So we say the space complexity is O of one itself if we implement it iteratively.
And that's how we are going to do it in this video.