Welcome back.
So we have successfully coded our binary search tree.
We have designed it and we have written the insert remove and find functions.
Now let's take a few samples and walk through the code to understand it deeper.
And again we will also look at the time complexity and space complexity of our solution.
All right.
So we start with the insert function over here.
Now what is happening over here.
We are calling uh the insert function.
Let's say we have called it and a value has been passed to it.
Let's start from there.
So let's say this is the existing binary search tree at this point.
And let's say for example we are inserting the value uh 75.
All right.
So let's say we are inserting the value 75.
Now what's happening.
We come over here.
Now we create a node right.
So only the value 75 is passed.
So at this point we create the nodes with value 75.
Then we check whether the root is null.
So the root is not null.
So this is not an empty binary search tree.
If it was then this 75 would have been set as the root over here.
Right?
Then we have a variable tree over here which is initialized to the root right.
And then we keep looping till we break out of this while loop.
So this while loop over here is ending right where it's ending over here.
So we keep looping it over in this while loop.
Now we are going to check whether the value which is 75 is less than three dot value.
So the value over here is 76.
And we see that 75 yes indeed is less than 76.
So what do we do.
We move in the left direction right.
So first we are going to check whether the left child of this node over here is null.
So that's what we are checking over here.
If tree dot left is null.
So if that is the case then we just insert it over here.
But if that is and then we return.
So we come out of the while loop.
And if that is not the case so what do we do.
We say tree is equal to three dot left.
So now initially tree was pointing to this node.
Now tree is pointing to this node over here.
And again it doesn't go to the else right.
It doesn't go to the else.
And we come back we loop.
It's still true.
So again we check the value.
Now value 75.
Is it less than three dot value three dot value is 50 in this case.
So it's not less.
So it does not go to the if loop over here.
And then it comes to the else loop.
So in the else loop we are checking.
We know that 75 has to be greater than or equal to 50.
Right.
So that's what is true.
Now we just check whether the right child of 50 is null.
So and in this case we see that it is null.
So if not tree dot right.
So that's it is null.
So it will come inside and we will say tree dot right is equal to node.
So this node over here will be placed over here.
So tree dot right is equal to node.
And that's how we successfully insert the node over here.
And we have seen that the time complexity of this solution is O of log n in the case of a balanced tree.
And the worst case will be o of n in the case of an unbalanced tree.
If it were looking something like this, right.
So in this case it's balanced.
So the time complexity will be O of log n.
And you can see that we are not doing we are not using any extra space.
Right.
We are not creating.
We are not having any recursive calls on the call stack as well.
So the space complexity of this solution is O of one.
All right.
Now let's proceed to the find function.
So this is the find function that we have written.
And we have a binary search tree over here.
Let's say we are trying to find the value 90.
All right.
So what do we do.
We pass the value 90 over here and we are inside the function.
Now we are checking whether the binary search tree is empty.
If it's empty then we can just return false because we won't be able to find anything in an empty binary
search tree.
Now, if it's not false, we come over here.
Right?
So that means the binary search tree is not empty.
Now we have a variable tree which is pointing to the root.
So tree is pointing to the root at this point.
Now we are going to loop through.
As long as this variable is not becoming null right.
So it will become null if we have searched through the entire tree and we have not found anything.
Let's also take a case where we are searching for 91, so we will see how we break out of the while
loop in this case.
Now we are checking whether value which is 90 is whether it is less than three dot value.
In this case three dot value is 76.
So this is not true right?
This is not true.
So we come to the else part.
And over here we are checking whether the value is greater than three dot value.
So yes 90 is greater than 76.
So what do we do.
We say three is equal to three dot right.
So we have three pointing to 80 at this point.
All right.
Now again it's still true right.
So the tree is still having a node.
So again we come to the while loop and we again come into it.
We loop through it again.
Now we are checking whether the value which is 70 uh 90 right.
The value is 90.
Is it less than three dot value which is not the case.
Right.
So again we come to the else part.
We see that 90 is greater than 80.
So again we move in the right direction.
So tree is now pointing to this node over here because we moved in the right direction.
All right.
So again tree is truthy right.
It's true.
Still.
So again we loop through in.
We again come to the while loop and we check whether the value 90.
In this case it's the value is 93, dot value is 90 and value is 90.
So is 90 less than 90.
No.
Is 90 greater than 90.
No.
So we come to the else if the third elseif over here.
And now at this case value is equal to the value right.
So these two are equal.
Therefore we return the tree.
That means we return this node.
So we have found the node which we are looking for.
And we return that particular tree and we come out.
So that's it.
So that's how the find function works.
Now let's say we were looking for 91 right.
So let's say we have reached till 90 and we were looking for 91.
Let me just delete this.
Remove this okay.
So let's say we were looking for 91.
And similar to the case where we were searching for 90 we have reached till 90.
Now again we check the it's still truthy right.
The tree root is still this is still a valid node.
So this is truthy.
So again we come into the while loop.
Right.
Let me just clear this up.
And then we check whether the value which is 91 is it less than 90.
No.
Right.
So no.
So we don't go inside over here.
Then we check whether 91 is greater than 90 which is over here.
Which is true.
Right.
So in this case we move in the right direction.
So tree is equal to three dot right.
So 3.3. right in this case is null right.
So now tree is pointing to null.
And then we come out and again when we check now tree is null right.
So null is falsey.
So we come out of the while loop and we just return false.
Which means that the there is no node in this binary search tree with value 91.
And again the time complexity of this solution is O of log n best and average, because that would be
the height, right?
If the tree is balanced.
And that's the number of comparisons we have to make to find or to be sure that that particular node
is not there in the binary search tree.
And the worst case will be O of n if it looks like a linked list, right.
Something like this.
If it's an unbalanced, uh, uh, binary search tree, and the space complexity over here you can see
is O of one.
We are not making any recursive calls on the call stack and we are not using any extra space.
Now finally let's look at the remove function.
So this is the remove function which we have written.
Now it's a lengthy part right.
So we have the remove function over here.
And this is the get min function which we have written.
And we have a uh sample binary search tree over here.
Now let's say we want to remove let's take one case each where let's start with the case where we want
to remove a node which has two children.
For example, let's say we want to remove 80.
All right.
So we want to remove 80.
So we are over here.
We pass the value 80.
And initially when we call this we don't pass current and parent.
So current is the root.
So this is the current at this point.
And the parent is null initially.
Right.
So we are initializing this over here.
Parent is null and current is this dot root.
Now we come inside we check whether the binary search tree is empty which is not the case.
So we come inside.
Now while current so current is truthy at this point because it's a valid node right.
So we are inside this while loop.
Now we are checking the value.
Value is 80 right.
Which is what we are passing over here.
We are checking whether 80 is less than current dot value.
Current dot value is 76.
This is not true right.
So we don't go inside this if loop.
Then we come over here we are checking whether value is greater than current dot value 80 is greater
than 76 which is true.
So we come inside this loop right inside this condition.
And then we set parent is equal to current.
So we make parent equal to 76.
And we say current is current dot right, right.
So what do we do.
We current was this.
So we just say current is current dot right.
So current will be 80 at this point.
All right.
Now what do we do.
Again.
We have done this operation so we don't go into the LS.
So the LS ends over here again.
We come over here now current is still truthy right.
This is a valid node.
So again we check whether the value is less than current dot value.
And in this case that's not the case right 80 and 80.
So 80 is not less than 80.
So it does not come over here.
Then we check whether 80 is greater than 80 which is not true.
So we don't come over here.
So we come to the else part, which means that we have found the node which is to be deleted, which
is this particular node, the current node at this point.
All right.
So let's proceed.
Now we start with the case where there are two children.
Right.
So over here we are checking whether current dot left is not null.
And current dot right is not null which is the case.
So we know that it has two children and we come inside over here.
Now we say current dot value is equal to this dot get mean.
And then we pass current dot right.
So we pass 90.
And so in this right subtree and in this right subtree there is just one node right.
So we just get the minimum value which is 90 itself.
So this function over here get min.
And where we are passing the node we will just keep going left and left till it reaches the minimum
value.
So if there was something over here let's say let's say we had um something greater than 80 which is
82 but less than 90.
So let's say we had 82.
Then the get min function would have returned 82.
All right.
So in this case it's going to return 90.
And what do we do.
We say current dot value is equal to 90.
So we set the value of this node over here as 90.
And then we call this dot remove.
So we call the remove function again.
But at this time we pass the value as 90.
So the value at this point is 90 right.
And then the current node is current dot right which is 90.
So we pass the node 90.
And then the parent over here the parent this is the third parameter is the parent right.
So the parent at this point is the current node which is this node over here.
Again it has the value 90 over here because it's same.
But let's say you had 82 over here.
Let's again just for understanding.
Let's have this case where we have 82 over here.
Right.
So in this case, we would have, uh, put 82 over here and then the value would have been passed as
82 and the current will be current dot right, which is 90.
Right.
And the parent will be this node.
It would have had the value 82.
Right.
This one over here.
All right.
So we are passing the current which we are passing this node.
We are passing this node and we are passing the value 90.
Now what will happen over here is again we are coming inside the remove function.
Now we, we have the uh the root the current is this dot.
The current is what what is current.
Let's just check that.
That's 90.
Right.
So this is current itself.
At this point we are taking the example where we don't have 82, so let's not get confused.
So we are taking the case where we are trying to delete this 90, right.
So we are checking whether current is truthy.
Yes it is.
And then we come inside and 90 is not less than 90.
90 is not greater than 90.
So we come to the else part and we see that we have found the node.
So over here again we check whether there are two children.
In this case 90 does not have two children.
So it comes to the else part.
Is the parent null.
No the parent is this node over here.
Right.
This one over here.
So it's we are not trying to remove the root node.
And so we come out of this else part and then we come to this part.
Else if current is equal to parent dot left.
So that's not the case.
This is a right child.
So we say current is parent dot right.
Which is true.
This is the parent.
This is the parent right.
Let me just clear this up a little bit.
All right.
So we place the value 90 over here.
This is the parent.
So current is parent dot right.
Yes that's the case.
So we say parent dot right is equal to if this has a child then we would have taken that child.
But it does not have a left or right child.
So we are just checking that over here.
Right.
If it will definitely not have two children because it did not go over here.
Right.
If it had two children it would have gone over here right in this if loop.
So we are sure that it does not have two children.
So it has only one child.
Now we are just checking the order does not matter.
We are just checking if there is a left child then say parent dot right.
Is that left child?
If there is a right child, let's say parent dot right is the right child.
So that's it.
So it will definitely have only one child if at all it has a child.
Now in this case we see that it does not have a child.
So we set this to null right.
So what.
How is it working.
We are checking if there is a left child.
No, there is no left child.
So we are setting parent dot right to its right.
So the right of this node over here is null itself.
So we are saying parent dot right is equal to null.
And that's how we have deleted this 90.
So at the end we will have 76 5043 over here.
And over here we will have 90.
There will be no right child.
This will be just null.
And the left child will be 78.
All right.
So we have taken care of the situation where we had to delete and we are deleting a node which has two
children.
So let me just make some space clear this up.
Now what happens if we are trying to delete a child, a node which has only one child or zero children?
So let's just take a look at those cases as well and run through the code.
So for this let's take two examples.
So over here we have 50 which has one child.
And let's say we have 78 which has no child.
So we are trying to delete these two.
So let's get started with the case where we have 50.
So we pass the value.
We come over here.
And again it's not an empty binary search tree.
So we have the node 50.
So we are starting with this the first case.
So we are checking whether 50 is less than 76.
Yes that's true.
So we move in the left direction.
So the parent is set to this and the current is over here.
Now again we come to the while loop again and we have the current as 50.
It's still truthy.
So we are checking whether 50 is less than 50.
No.
Is 50 greater than 50.
No.
So that means we have found the node and we are over here.
Now we are checking whether 50 has two children which is not the case.
So we come over here is 50 is parent null or are we checking.
We are checking whether 50 is the root node which is not the case.
So then we come over here and we are checking whether 50 is a left child, whether 50 current is parent
dot left which is true.
So we come inside over here and we say parent dot left is its child.
So we are just checking whether this has a child.
It will definitely not have two children right.
Because in that case it would have gone in over here.
So it has only one child if at all it has a child.
So we are checking does it have a left child.
Yes it has.
So we say parent dot left is the left child of 50 which is this.
So we are removing this node and we are making this connection over here.
So we have removed this node.
All right.
Now what happens if we are just trying to remove a node which has no children for example 78.
Let's just clear this up.
All right.
So if you are trying to remove 78 again we start at the root right.
We have 76.
We we are comparing the values.
Is 78 less than 76.
No.
Is 78 greater than 76.
Yes.
So we say parent is equal to current which is this one.
So this will be the parent again.
And current is current dot right.
So current dot right.
Is this one over here.
So this is current which is 80 right now.
Again uh we come back and it's still truthy.
Now we are going to check whether 88 and 78.
So 78 is the value right.
We see that 78 which is the value is less than 80.
So 78 is less than 80.
So we move in this direction right.
So we say current is current dot left.
And again we come to the while loop and we check and current is truthy.
So this is current at this point.
And this is the parent at this point.
Now we see that the value is 78 is not less than 78, 78 is not greater than 78.
So we come over here to the else part and we have found the route which is to be the node, the node
which is to be deleted.
Now we are checking whether this node has two children.
No it does not have two children.
Is this node the root.
No it's not.
So we are just checking is this a left child or a right child.
We see that it's a left child.
So we come over here and we say parent dot left is any child if it has.
So we are checking whether it has a left child.
Does 78 have a left child.
No.
So in that case we are just assigning parent dot left as the current dot right.
Current dot right over here is null.
So this is null.
So what we are doing is parent dot left is null.
In that way we are removing this node.
All right.
So we have seen all the three cases.
Now let's also see the case where we are trying to remove the root node.
So what's happening over here.
Let's just quickly see that as well.
So let's say we are trying to remove 76.
So we come over here.
We will again go through all this part, and then we will have found the node because the value is equal.
Right.
So we come over here and it has two children.
So it has two children.
So what do we do.
We.
Find the minimum value of the right subtree over here.
Get min value.
So we'll get 78.
And we will say current dot value is 78.
So this will be 78.
Then we will call the remove function on this subtree right.
So we are going to pass.
80 as the current node.
This is the current node.
This is the parent node and the value to be deleted is 78.
Again, we will find that this is a node with only one child and this will be deleted.
So that's how it works over here.
Now let's also see the case where we have just the root node right.
So let's just see that also as well.
Let's say the binary tree was something like this 76 and let's say it had one child 50.
So what do we do in this case?
In this case, again we are trying to remove 76.
So we will come over here.
We will come, we will we won't come inside because it does not have two children.
So we come over here and we see that yes, it's the root node or its parent is null at this point right.
Parent is null.
So we are trying to remove the root node itself.
Now we are going to check whether current dot left is null.
So current dot left is not null.
So in this case yes we have something over here.
So what do we do.
We put this value 50 over here and it's left and right will be put over here left and right.
In this case it's just null.
So in this way we will have removed, uh this 76.
And we'll just have one node and that will be the root node.
And it has 50 as value.
And it's left and right is null.
Now let's say again we are removing 50.
So this is the scenario.
Now we just have one node in the binary search tree.
And its left is null and its right is null.
And let's say we are trying to remove the node with value 50.
So what happens again we will check the value and we will see that it's equal.
So we will come over here.
Now we see that it does not have two children.
So we come over here we see that its parent is actually null.
So we come over here and we see that it does not have a left child and it does not have a right child.
So we come over here so we understand that we just need to remove a single node.
And the binary search tree has only a single node and it's the root itself.
So in this case we just say that the root is equal to null.
So in this case the we are just deleting the binary search tree and its root itself is null.
So that's how the remove function works.
All right.
So let's quickly take a look at the complexity analysis.
So the time complexity of this solution will be O of log n average.
And best case because if the tree is balanced that is the height of log n is the height of the balanced
tree.
Right.
And it will be O of n if it's an unbalanced binary search tree.
Something like this.
We have already discussed that right now the space complexity you can see is equal to O of one.
We are making only one recursive call right over here.
Right.
So you can say that the space complexity is O of two.
But then this is just a constant.
So we get that the space complexity is equal to O of one.
So this is the iterative solution where we where we implement the function remove to remove a node from
the binary search tree.