Welcome back.
Let's now go ahead and code the solution which we have already discussed.
Now over here we will be creating a class node.
Because each of these values is going to be a node.
Right.
So we will have a class node for this.
And then we will have our class binary search tree.
Right.
So let's write that over here.
This is binary search tree.
And using this class, we will create a new instance.
Write a new instance object of this class.
So let's call that uh.
Let uh, let's call it BST is equal to new binary search tree.
And then we will call the functions which we are going to write on this object.
Right.
So we will have BST dot insert for example 20.
So this is the first part which is to write the insert function.
Right.
So we have to write the insert function the find function and the remove function.
So let's get started.
And over here I've just uh written this out over here so that we can visualize.
It's easier to visualize like this right.
So I have this over here.
So using the insert function which we have we are going to write.
We will create this binary search tree.
Now let's get started.
Now for the class node we will have the constructor.
So let's write the constructor.
And we need the value to be passed in over here.
And we say that this dot value is equal to the value which we passed.
And we say this dot left is equal to null.
And this dot right is equal to null.
So for each node initially, we will have the left and right pointing to null.
And then when we call the insert function, we will place it at the correct place in the binary search
tree, so that the binary search tree property is fulfilled.
All right.
Now let's go ahead and write the constructor for the binary search tree class over here.
And we say.
This dot root is equal to null.
We are not passing any value, we just setting the root to be null.
All right.
Now over here we will write the instance method.
So we'll have insert.
And we will be passing the value.
All right.
And we will also write the find method.
And again we will be passing the value.
And it will either return the node or it will return false.
If the value is not found in the binary search tree.
And then finally we will write the remove function where again the value is passed and that particular
node will be removed from the binary search tree.
All right.
So this is what we are going to do.
Now let's get started with the insert function.
Now initially let's say that we have this instance object over here we have BST.
And this is empty initially.
And let's say we are calling BST dot insert 20.
So we come over here.
And at this point the binary search tree is empty right.
So we need to set this 20 as the root right.
So the root is null.
So we need to set the 20 as the root.
So let's go ahead and do that.
So first we say that.
Uh, let's say const.
New node.
Or let's just call it node is equal to new node and we pass in the value.
All right.
Now we are going to check whether the root is null, right?
If not this dot root, that means the root is null or the binary search tree is empty.
If this is the case then we say this dot root is equal to node and we are done right.
We can just return this.
That is, we are returning the whole binary search tree.
All right.
Now if this is not the case we proceed further and we let's have a variable let's say tree.
Let tree is equal to this dot root.
Because we need to find the correct position right where to insert the particular node.
So let's go ahead and check that.
So over here we say that tree is the root at this point.
And then we loop over the binary search tree.
And let's say while true and at some instance at that is at the point where we have already found the
correct place and inserted the node, we will exit from this while loop.
All right.
Now what we need to do is we need to check whether the value is less than the value of the node.
So if value less than three dot value.
Right.
If this is the case, then we have to move left.
Right.
So we have to move left.
So let's just write a comment.
Move left.
Now if this is not the case, if if this is not the case then what we do we move right?
So that is how we find the right position where the node has to be inserted.
Right.
Let's take this example.
Let's say we have already inserted 20 and let's say we are trying to insert six.
Now we are over here, we see that six is less than this value 20 right.
So we have to move left.
Now let's say we have already inserted six and 35 and we are trying to insert 27 for example.
So in this case we start again at the root.
And we see that 27 is greater than 20.
So we move right right.
And then we have 35.
We see that 27 is less than 35.
So we move left and we find the place.
So just imagine that at this point these are not inserted.
So over here we will have null right.
So if we find that this is null we can just insert it over here.
So that is what we are going to write over here.
So let's go ahead.
So if value is less than three then we move left.
So first we check whether the position at tree dot left is null.
So if not tree dot left then we can just insert it over there.
Right.
We don't need to move.
Actually we can just insert it over there.
So let's write that.
So in this case we can say tree dot left is equal to node.
And then we are done.
Right.
We can just return the binary search tree and exit.
But if that is not the case we move left.
That is three is equal to three dot left.
All right.
So what happened over here?
Just imagine this is not there right.
Let me just write it like this.
So if this is not there and we are trying to insert 27.
So again we are at 20, we come to 35.
And then we move left and we see that there is nothing over here.
Right.
So then we can just insert it over here.
So that's what we have done over here.
We have checked whether tree dot left is null.
And if that is the case then we just assign the node to tree dot left right.
Now if over here for example again 27 was there.
And let's say we are trying to insert 25.
So again we came to 35.
Then we move left.
And at this point right again we are at this point where we are 35.
We are trying to match with the previous example, right.
So we are at 35 and we see that we have to move in the left direction.
But this is not null.
So what do we do.
We again move tree is equal to three dot left.
So we come over here and then we check its left and right.
So that's the procedure.
All right.
Now in the else case right.
So this will happen when the value is greater than or equal to the value at tree right.
So tree dot value.
So that's the case which is the else part over here.
So notice that it's not only greater it's also equal.
For example in this tree in this example which I have written over here, you can see that we have three
over here and we have three over here.
So let's say we are trying to insert three.
And so only this is not there.
So I'm just removing this.
So imagine over here we have null.
So and we are trying to insert three.
So we start again at the root and we move left because three is less than 20.
We move left because three is less than six.
And we are over here.
Now we are checking whether three is less than three which is not true.
Right.
So it will not come over here.
It will not come into this part, but it will come into the else part.
And we see that its right is null.
So we will just insert it over here.
So that's what we are doing over here.
All right.
So if the value is greater than or equal to three dot value we either move right.
Or if that position is null we insert it over there.
All right.
So let's check whether that position is null.
So if not three dot right.
In that case, we just insert it, right?
So we can say tree dot right is equal to node and we are done.
And we can just return this.
All right.
Now if this is not the case, if we don't have a null over here then we have to move in the right direction.
And for this we do tree is equal to three dot.
Right.
All right.
And we are done.
We are done with the insert function.
All right, so let me just clean this up a bit.
Now.
Let's go ahead and call the insert function to create this binary search tree, which I've written over
here.
Right.
So let's just take it down.
All right so that we can see it.
So we have 20.
So 123456789 ten 1112.
So this is 12 elements.
So let me just write this 12 times.
So this is one.
23456789 ten 1112.
So 20.
Then we have six.
So let's quickly write that we have six.
Then we have 35.
Then we have three and eight.
All right, so let's write eight.
And then we have 27 and 55.
And one three.
And 2529.
And 60.
All right, so let's run this.
And let's take a look at our binary search tree.
All right.
So this is the expectation right.
So we have the expectation over here.
So let's take a look.
The root node is 20 which is correct.
And on its left we have six.
And on its right we have 35.
All right.
So it inserted in the correct position.
And for six the children are three and eight which is correct.
For three the children are one and three.
Notice that three is on the right.
Right as we have discussed.
And for one it's null and null, and for three it's also null and null.
So yes this is correct.
And for eight again there are no children.
So it's null.
So this part is correct.
Now what about this part.
We have 35 over here and its children are 27 and 55 which is correct.
Now the children of 27 are 25 and 29.
And they don't have any children.
All right.
So this is correct.
And then for 55 we have only one child, the right child which is 60.
And the left child is null.
So this is correct.
Right.
So we have successfully coded our insert function.
All right.
So this is pretty straightforward.
Now let's go ahead and do the find function.
This is also pretty similar to the insert function right.
We have to just go to the correct position.
And we have to see if the value is there or not.
So let's go ahead and do that.
Now again the value is passed over here.
Now once inside this we have to check whether it's an empty binary search tree.
So let's do that.
If not this dot root.
So that means that the binary search tree is empty and we can just return false.
Right.
So we won't be able to find anything over there.
Now, if this is not the case, let's create a variable.
Let tree is equal to this dot root.
So we will start searching from the root.
Now again we will keep looping.
And now let me write Wild Tree.
So as long as tree is not null, right, we will keep looping.
As long as we are not reaching null for the node, we will keep looping and searching and we'll keep
searching for the value.
Now what we have to do is we have to see whether the past value is less than the node value, the value
at the node.
So let's say if if value less than three dot value.
Now, if this is the case again, we have to move in the left direction, right?
For example, if you are searching for three.
So again we are at the root which is 20.
Now three is less than 20.
So we have to move in the left direction.
Again three is less than six.
So we have we have to move in the left direction and we find it right.
So if value is less than three dot value then what do we do.
We have to just move in the left direction.
So three is equal to three dot left.
All right.
Now, if this is not the case, else if value is greater than three dot value.
In this case, we have to just move in the right direction.
P is equal to three dot, right?
Finally, if we have found the value.
Else if value is equal to three dot value.
So in that, that means that we have found the node, right?
The node with the required value has been found, and we can just return that particular node in that
instance.
And then finally, if we are out of the while loop and we have not found anything as mentioned in the
question, we will just return false and we are done with our find function.
So let's go ahead and test it out.
And we get the node.
All right.
So it's working.
So we got that particular node right.
And it's left and right are pointing to null which is also correct.
Right which we have visualized over here.
Now let's try 35.
And we get the node 35 and it's left is 27 and its right is 55, which is correct.
So yes, our find function is also working.
Now let's proceed and go ahead and write the remove function.
All right.
So I'm just clearing the console.
Now over here we have the remove function.
Let me just clear this space.
Now in the remove function.
Also, the way we go about this is that, as we have discussed in the previous video, there are three
particular cases right now.
If the node to be removed has two children, then we have to find the lowest value in the right subtree.
Or we could find the highest value in the left subtree.
So either one of these ways works.
So over here we will go ahead and find the lowest value in the right subtree.
So that's how we will remove it.
And if it's just a leaf node we can just replace it with null.
And if it's a node with only one child then we can just connect the parent with that particular child.
So we have discussed these cases in the previous video.
Now over here let's go ahead and implement this function.
And before this again let's write um function.
We will also need a helper function.
So I'm just making a placeholder for it.
So let's say get min.
And over here we will pass a particular node right.
So we'll pass a particular node.
And then we want to that node will be treated as the root.
Right.
So it's a subtree actually with the root as this particular node.
And in that subtree we want to find the minimum value right.
Because we will use this when we want to find the minimum value in the right subtree of that particular
node, which has to be deleted.
And for the case where that node has two children.
All right.
So over here I'm just having it as a placeholder.
We will come back and write this function when we need it.
Now let's get started with the remove function.
Now over here I've written that we are passing the value.
Let me add two more things over here that we are going to pass to this function.
So we will add the current node and we will add the parent node over here.
Now why are we doing this.
For example let me just explain that over here.
Let's say we are trying to remove 35.
All right.
So we know that the lowest or let's say we are trying to remove 20 now in this if we are removing 20
the lowest node in this right subtree right is 25, right.
The lowest value is 25.
So we have to put 25 over here.
So I'm just doing that over here.
I have to put 25 over here.
And then I have to remove this right.
I have to make this null.
So what we will do is so I'm just putting it back.
So this is 25.
So what we will do is we will find the minimum value which is 25, using the get min node for this case
where there are two children.
And we will put that over here.
Initially this was 20 and we changed this to 25.
And then we will again call the remove function one more time recursively on this subtree.
And we will pass 35 as the node right.
So and then we will pass 25 as the value.
Earlier we had passed the value as 20.
But now we just need to change this 25 to null right.
So to be able to do this in a recursive manner, that's why I'm writing this over here.
Current and parent.
Right.
So initially when nothing is passed we will take current as the root node.
So let's write this dot root over here.
And the parent will be null because the parent of the root node is null.
Now now when we call this recursively for example again I am writing 20 over here so that this is the
binary search tree.
And this is 25 right now when we want to remove this 20 right.
We put this 25 over here.
And we will recursively call the remove function this function over here on this subtree which has 35
as the node and as the root.
And these are the other nodes.
Right.
So in this case we will pass 35 as the current node.
And the parent of 35 is 25 at this point.
So again we will revisit this once more when we write this.
So for now let me put this back.
Put this back to 20 and let's proceed.
So we have the remove function and it has three parameters passed to it.
Value the current node and the parent of the current node.
At this point.
Initially the current is the root and the parent is null because the parent of the the the root node
does not have any parent.
All right.
So let's go ahead.
Now what we have to do is first we check whether again as we did in the other cases, whether the binary
search tree is empty or not.
So if not this dot root then we cannot remove anything from it.
Right.
So in that case we just oops.
Yeah.
If not this dot root, in that case we just return false because we cannot remove anything from it.
All right.
So we just come out of the loop.
Now let's proceed.
Now we have to loop through while current node is true.
All right.
So this is the current node.
And then we will break out of this loop.
At some point we will discuss this as we go ahead.
Now first we need to find the node which has to be removed.
Right.
So that's the first thing that we are going to do.
So let's look at the value.
So if value less than current dot value in that case we just need to move in the left direction right.
So let's write that.
So moving in the left direction means we are setting the parent as the current node.
And we are setting the current node as current dot left.
Right.
So we had current over here.
We see that the value of current is less.
Uh, the value is less than the value of the current node.
So we have to move in the left direction.
So that's why we do this.
Current is equal to current dot left.
But we don't want to miss the value of the parent.
Right.
Because we need to make some connections in some cases from the parent to the child etc..
Right.
So we need to keep track of the parent.
So when we move the current to current dot left the parent becomes current.
So that's what we have done over here.
All right.
Now let's proceed.
If this is not the case right.
So let's write that else if.
If the value is greater.
Value is greater than current dot value.
In this case, what do we do?
We have to move in the right direction.
So again it's similar to what we've written above.
So the parent is set to current and the current is set to.
Current dot, right?
And we move in the right direction.
All right.
So again finally, if this is also not true, else means we have found the node to be deleted.
All right.
Now let's proceed.
Now there are three cases as we discussed.
Right.
So there is a possibility that the node to be deleted has two children or it has one child or it has
zero children.
So let's think in that direction.
So first we deal with the case where the node to be deleted.
Has two children.
So let's deal with that case first.
Now, if this is the case, what?
How can we identify it?
We can check whether the current node has a left child and a right child.
Right.
So current dot left should not be null.
And.
Current dot, right?
Should not be null.
This means that the node which is to be deleted has two children.
Right?
So what do we do in this case?
In this case we have to find for example, let's say we are again trying to remove this node over here,
which is 20.
We have to find the minimum value in the right subtree right.
So the right subtree starts with 35.
And then you have 2755 and 2529 and 60.
So the minimum over here is 25.
So we need to find that value and change the value of the current node to that value.
Right.
So we need to put this 25 over here.
So we have discussed that right in the previous video.
So let's look at the code to do this.
So we say current node.
Dot value is equal to the value that we return from this function.
This is the help of helper function which we will call at this point.
So we say this dot.
Get mean, and then we have to pass the right.
Uh, node of this, right?
The current node is, for example, at 20 we need to find the minimum in the right subtree.
So the right subtree starts at 35.
So we have to pass this particular node over here.
So this will be current dot right.
All right.
So we are passing current or right to this, uh, function so that it will return the minimum value.
So let's at this point go ahead and write the helper function over here.
Now, what is the helper function supposed to do?
It has to go.
It has to continuously, in an iterative manner, go left and left till it reaches null.
Right.
So let's write that over here.
So we have know the node.
This 35 for example in our example is passed over here.
Right now we are going to loop while node dot left.
So while node dot left is not null right.
So let's just write it.
So as long as it is not null we'll just move in the left direction.
So we say node is equal to node dot left.
Now when we come out of this while loop we will have reached node dot left is null right.
So we are at the leftmost position of the right subtree which is the lowest value.
At this point we just need to return the value return node dot value.
And that's it.
That's the helper function.
So when we called our helper function over here.
All right.
So this is wrong.
Yeah.
So when we call the helper function over here, it will find the minimum value in the right subtree
and return it right.
Because we we are returning that value over here.
And that value will be assigned to current dot value.
So for example over here if you are trying to delete 20 the minimum value in the right subtree, which
is this part over here is 25.
So we find it the helper function will return 25 and we will set this value as 25.
Now what do we need to do next.
We need to remove this right.
We have to set this to null.
So for this we will recursively call the same remove function right.
So let's go ahead and do that.
But at this point we will pass the current node and the parent node right.
So that's the that's the difference.
That's what we discussed over here.
That that's the reason we are passing.
We are having these parameters for the remove function.
So let's go ahead and do that.
This dot remove.
So let's write that it will be over here.
So this dot remove.
And then what is the value that we want to remove.
It will be the current value at this point.
Right.
Which is this 25.
It's not 20.
We have removed 20 by putting 25 over here.
Now we just want to remove 25 right.
So the value which I pass over here is current dot value which is 25 at this case for our example.
And then we will pass the current node and the parent of the current node.
So current node let's dot write right current node dot right.
That's the first note in the right subtree, and the parent of this node is the current node.
Right or current.
We call it current over here.
All right.
So what this will do is it will recursively call the remove function on this right subtree.
It will search for 25.
And it will see that 25 is over here.
And it will replace this with null.
Now let's look at one more case.
Let's say for example over here 25 was not the ending.
And you have a right child for 25.
Let's say that's 26.
So is that correct?
26 when we enter it's less than 35.
It will come over here.
27 it's less than 27.
It comes over here.
It's greater than 25.
So it comes to the right.
So yes it would be inserted over here.
I'm just making this correct.
All right.
So what would happen in this case.
Again we found 25 as the minimum value.
We placed it over here.
This was earlier 20.
Now when we recursively call the remove function on this right subtree this part right it will find
25.
And then it will make this connection 27 and 26 will be connected.
So this 25 will go and we will have 26 over here.
All right.
So we have discussed this in the concept video also.
All right.
So for this that's why we are calling the remove function over here recursively.
And that's what is happening over here.
Now when we do the code walkthrough let's again visit this so that you are very thorough with what with
what is happening over here.
All right.
So we have dealt the case where the node to be deleted has two children.
And that is over with this.
Now let's proceed.
The next case that we have to look at is if we are deleting the root node.
Now, why are we treating this as a separate case?
Because over here there is no parent, right?
So that is one point when you're deleting the root node, there is no connection with the parent of
that node that you have to make.
Secondly, if the binary search tree has only one node and that node is the root node and we are trying
to delete it, then we have to set the root to null.
So these are the two points to be kept in mind.
So let's proceed.
Now how do we check this.
Else if parent is equal to.
Null.
This is the case where we are trying to delete the root node, and the root node does not have two children.
So we are also aware of that because if the root node had two children it would come over here.
Right.
So that would have taken care over here.
So over here we are checking whether we are deleting the root node.
And it does not have uh two children.
All right.
So let's proceed.
Now if this is the case, first we check whether it, it has, let's say a left child.
We could do it in either order.
So let's say current dot left.
Not equal to null.
So that means there is a left child, right?
So we have to make that left child as the root node in this case.
And again remember it does not have a right child if it is having a left child.
If you are reaching over here, it does not have a right child because if it had two children, we already
have taken care of it over here.
So again remember this is if it has one child and that's the left child.
So if that is the case, what do we do then we have to set the the root as the left child.
So let's go ahead.
So current dot value has to be the value of the left child right.
So current dot left dot value and then the left child.
If it has a left and right connection, that connection has to be made to the current node.
Right.
So we say current dot left is equal to current dot left dot left.
And we can say current dot, right?
Is equal to current dot left, dot right.
So what's happening over here?
Let's try to visualize this.
Let's say our tree looks like this.
For example we have 20.
Let's again put this 20 over here which is the example which we have taken.
And let me just modify this a little bit for our example.
I'm just removing 35 over here.
I'm just keeping it over here so that I can keep it back.
Right.
So we are just using this example to look at various scenarios.
Let's say our binary search tree looks like this.
We have 20 and we have six.
And we are trying to remove 20.
So this node over here is the root node.
It does not have two children.
So it will not come over here.
And we are over here now we are over here.
We see that it's the parent node.
Yes.
And we see that the left child is not null.
So we have six over here.
Now in this case again let me just modify this a little bit.
Let's put three and eight also over here for clarity's sake.
And I'm just removing these also.
All right.
So let's say this is the binary search tree which we have at this point.
Now if you are trying to remove 20, what do we need to do.
We have to put this six over here.
Right.
And then this node should be connected to this three and eight.
There's nothing over here.
Right.
So I can just remove this.
Let me just take it to the right because I want to bring this back.
So there's nothing over here.
Right.
So after we do the deletion what should happen.
We should get six over here.
And we should have three and eight.
As its children.
Right.
So over here we should have three.
And over here we should have eight.
And that should be the right child.
Right.
So it should look like this.
All right.
So that is what we are trying to do over here.
Right.
So we are setting the value of the current node as the value of the left node.
And this left and this right is set to the left and right of the current dot left node.
So current dot left is a node and its right is set to the right of current node, and its left is set
to the left of the current node.
That is what we are doing over here.
So let me just undo these changes so that we have our example over here intact for other cases also.
All right.
Now let's proceed.
Now, if this is not the case, right?
If this is not the case, let's proceed.
Else if.
And let's say we say that we see that it has a right child.
So if current dot right.
Is not equal to null.
It's similar.
Similar right.
In this in this case we have to just set current dot value.
Is equal to the value of the right child, which is current dot right dot value.
And we have to say it's left and right.
That is current dot left and current dot right.
Has to be set to the left and right of the right node.
So we have current dot.
Right, which is the child which is existing.
Right.
So let me just write this over here for conceptual clarity.
Again, over here also we have current dot right.
And now the left child of the current node has to be set to the left child of current dot right.
So dot left over here.
Similarly the right child of current has to be set to the right child of current dot right.
So this is current dot right dot right.
All right.
So we have covered these cases.
So this is the case where we are trying to delete the root node.
And it has one child right.
So the one child which each it has if it's the left node we do this.
If the child which is there is the right node we do this.
Now there is one more case which is the else part.
This means that this is just a single node tree.
Single node binary search tree.
And we are trying to remove the root.
Right.
So we are removing the root.
In this case we have to say this dot root is equal to null.
All right.
So we are done with the case where we are trying to remove the.
Root node.
Right.
And we have also taken care of this special case where if it's a single node and we are trying to remove
the root itself, we have to set the root to null.
Now let's check the case where the node which is to be removed either has zero children or one child.
Now there are two possibilities.
That particular node which is to be removed, can either be the left child of the parent or the right
child of the parent.
So let's check that else.
If current node is equal to parent dot left.
In this case we do something.
So let's just write placeholders for now.
Or else if.
The current node is the parent node, right?
The right child of the parent.
And in this case also we do something.
So let's discuss this now.
For example over here I have 55.
Let's say 55 is the node which is to be removed.
Now 55 is the right child of the parent.
Right.
So in this case we have to say parent dot right is equal to this 60 over here.
Similarly let's for example remove this 29 for now.
And again 27 has only one child 25.
So let's say we are trying to remove 27.
In this case 35 is the parent and its left has to be set to 25.
Right.
So that's why we need to know whether the node which is to be removed in 27 and 55, the two examples
which we discussed is a left child or a right child of the parent.
So that is what we are checking over here.
Now if it's a left child then we set parent dot left right.
Is equal to the child.
Now we are saying that it either has one child or zero children, right?
So if it has one child, whichever that child is, whether it's a left child or a right child of current.
We said that.
Right.
So parent dot left should be that node.
So let's check it.
And if it's if it does not have any children parent dot left will be equal to null.
So that is what we are trying to write over here.
So let's check whether current dot left is not null.
If it's not null, then we we put current dot left.
That parent dot left should connect to current dot left.
Now, if it is null, if it is null, then the other child, right?
So current dot right.
Now in case both of these are null, in case current dot left is null, either current or right could
be a child node or it can be null.
So that's fine right?
So if there is no children then parent dot left has to be set to null anyway.
So this is correct.
Similarly over here also because we find that the current node is the right child of the parent, we
have to say parent dot, right.
Is equal to.
So we just check whether there is any child.
So the same thing can be done.
Current dot left not equal to null.
That means if there is a left child then we have to do parent dot right is equal to current dot left.
Now if that is not the case, then parent dot right is equal to current dot right?
So if there is a child that child would be assigned that node will be connected to parent dot.
Right.
And if there is no child parent dot right will be null.
And then we are done with this.
Now at this point we have to break out of the while loop.
So let's just write that.
So we write break.
So what does this mean.
So we have come to this else part right.
That means we have found the value which is to be deleted.
Right.
So once we are inside, any one of these will be executed.
Right.
Because we have found the value to be deleted.
So by by reaching over here, we have to come out of this loop.
We don't need to keep again repeating with that particular current node.
Because if you don't write this then this would be an infinite loop, right?
Because current is now some node, right?
So current is still true.
So this will never end.
So once we are done with the removal which is this part over here, right.
Else means we have found the node to be deleted.
So inside we go ahead and do the deletion and we break out of it.
All right.
So we are done.
And at this point at the end we just return the binary search tree.
So return this and we are done.
Let's go ahead and test our code.
So we have our binary search tree.
So this is the binary search tree which we have.
Now let's try to take one case of each.
We are trying to let's try to remove a node which has one child.
And let's try to remove a node which has two children and a node which has no children.
So let's go ahead and do that.
So first let's just remove 60 over here which is a leaf node.
All right.
So this 60 should have gone.
So 55 should just have no children at this point.
So let's go in this branch which is 35.
Right.
So 35 2755.
And then 55 has no children.
So this is working.
All right.
So let's proceed.
And we have removed 60 at this point.
Now let's go ahead and remove 29 so that I can make 27 a node with only one child.
So let's just remove 29.
All right.
So let's look at the binary search tree.
Now we have 20.
And over here we have 3537 has 2755.
And what about 2727 has only one child which is.
25.
Right.
The left node is 25.
The right node is null.
So this is correct.
All right.
So let's proceed now.
Now we have removed 29 also.
Now we're just going to remove 27.
And this is a node which has only one child.
So this should be working.
So let's check that.
All right.
So we have removed 27.
Our expectation is 35.
Should have now two children 25 and 55.
So let's check that 20 then 3535 has two children 25 and 55 which is correct.
Five now let's say we want to remove 20.
So 20 has two children.
So let's do that case.
Now what is the expectation?
This is the right subtree 35 2555 so the expectation is this 25 should be made the root.
And then this should be removed from here.
Right.
So that's the expectation.
So let's go ahead and look at it.
Now when we run this we can see yes this 25 is the root now.
So we have 25 over here which is correct.
And then this 25 should be removed.
Right.
So let's just remove it over here.
And the children should be 35 and 55.
The child of 35 is 55.
So let's check it 25 has two children six and 35 which is correct.
And 35 has only the right child, which is 55, 55 has no children.
So yes, that's also working.
All right.
So yes, our code is working.
Now let's take a few samples and walk through the code that we have written to analyze it better and
understand it.
And we will also quickly relook at the complexity analysis of this solution.