Welcome back.
Let's now think how we can solve this question.
Let's say the array which is given to us is one, two, three, four, five.
And let's try to make a few observations.
Now we know that we have to convert this into a height balanced binary search tree.
And for this we will have some element.
Some element among these values is going to be made the root right of the binary search tree.
Now we know that this will be height balanced only if the depth of the two subtrees does not differ
by more than one.
So this means that we should have the same or almost the same number of nodes in the left part and the
right part of this root node right.
This is the left part and this is the right part.
Now if you're just filling everything into its right and nothing into its left, then this is not going
to be height balanced.
So to make it height balanced, that is to ensure that the depth of the two subtrees, the left and
the right subtrees does not differ by more than one.
We have to have the same or almost the same number of nodes in the left and right of the root.
So this is an interesting observation.
So this can be possible if we just pick the middle value as the root right.
Then you can see that we have an equal number of items towards its left and towards its right.
Now why do we have almost the same over here?
For example, if the array which is given to us is one, two, three, four, five.
Now if you are taking the middle as left plus right divided by two, that is, this is index zero.
This is index one, this is two, this is three.
So if you do zero plus three by two and then we are flooring it, we will get one as the middle element.
Right.
So this would be the middle element.
Now on its left we just have one element.
And on its right we have two.
But that is okay because the depth can differ by one.
So that's not a problem.
So that's why we have almost the same.
So we need either the same or almost the same nodes in the left and the right of the root.
So that means that we have understood we have to pick the middle value in the sorted array, which is
given to us, and make it the root of the binary search tree.
And again, remember the array which is given to us is strictly increasing.
So we just have to pick the middle value.
There is no possibility that this is going to be two.
This is two and this is also two etc..
Right.
So because it is strictly increasing.
So we just have to pick the middle value and we can be sure that there's going to be the same or almost
the same nodes in the left and the right of the middle value.
All right.
So this is an interesting observation.
So let's go ahead and try to implement this and proceed with our solution.
So over here let's say this is the array which is given to us.
And let's write the indices of the given array.
So we have zero till eight as the indices.
And we are going to have a left pointer and the right pointer to identify the middle value.
Now middle at this point is going to be zero plus eight by two.
And then we're just going to floor it which is equal to four.
So we get that middle is pointing at index four which has the value five.
And as we've seen in the previous section we are going to make this the root node.
So let's make a node out of this.
And this is going to be the root node of the binary search tree.
So we have already used this up.
All right.
Now what we are going to do is we are going to recursively call the same function on the left part,
which is this part and the right part of the array.
And we are just going to make notes.
Right.
So we are just going to do this recursively.
So always the middle value is going to be made into a node.
And then it's going to be either the left node or the right node for the particular node where we are
at.
So let's try to understand this in a better manner.
Now why do we need to do this.
Why do we need to keep recursively doing this.
Now let's try to make an observation.
So we have already got five as our root node.
Now we cannot just insert all of these values in any order on the left side of the particular root node.
Right.
We cannot do that.
That alone will not be sufficient.
Why is that so?
Because I could have an insertion like this.
I could insert one towards its left.
And then if are if we are inserting two, three and four towards the left of the node five, it's all
going to be over here because these are greater than one right now.
In this case you can see 1234.
So we have four nodes.
And there is nothing over here.
Right.
So you can see this is not going to be height balanced.
This part over here is not height balanced.
So you have 01233 edges over here.
And you have zero edges on its left part of this particular node.
So this is not height balanced.
So that's why we cannot do it simply in this manner.
But we have to recursively call the same function with which we created the node to go ahead and process
the other nodes as well.
So let's go ahead and take a look at how we proceed with this.
And the best way to understand this is by just walking through it.
So let's try to see how we go about with this now because this is going to be a recursive solution.
Let's keep track of the call stack.
So this particular call where we created the node with value five was when we passed left to be equal
to zero and right to be equal to eight.
So let's write that in our call stack.
So we have zero eight.
So left is zero and right is eight.
And with this call we identified the middle as five.
And that was made to a node.
So that is where.
We are at now, we are going to see how we will recursively call the same function towards the left
part, which is this part and the right part.
All right, so let's proceed.
Now first we will go with the left.
So that is this section over here.
So you can see that the left extreme over here is zero itself.
And the right is middle minus one which is four minus one which is three.
So we are going to make a call to the same function.
And left is going to be zero.
And right is going to be three.
So let's write that in our call stack.
So we have zero comma three over here.
And once we are out of this right.
Once we are out of this we will process the right.
So that's going to be a call where left is going to be middle plus one which is five and right is going
to be eight itself, which is this part over here right now.
Let me just write this over here as a placeholder.
So once we go deep and once we come back, right, once this processing is over, we will go ahead and
process the right, which is calling the same function by passing left as five and right as eight.
So let's proceed.
Now we are in this call where left is zero and right is three.
Again we calculate middle as floor of zero plus three by two, which is equal to one.
So at index one we have the element two.
And this was part of the left call right.
So this was part of the left call.
So that's why this this value over here is going to be made a node and made the left of this particular
node.
All right.
So we have two over here.
And that's the left of this particular node again that we we know that this is going to be left of this
node because this was part of the left call.
Right.
So let's proceed.
And we know everything to the left of something is going to be less than that value.
Because the array which is given to us is sorted.
So let's proceed.
So we are done this much.
Now again a side note quick side note over here.
We could ideally just go ahead and identify that we have to insert two next.
And then we can just call the insert function for the binary search tree which is an instance method.
Right.
Which we have previously written in a previous question.
So we could do that.
But that would be a O of log n operation, because we know that inserting into a binary search tree
is a o of log n operation.
So this is not efficient because we could do it just in constant time, which is a O of one operation,
because we know that this has to be the left of this particular node, because this was called on the
left part.
Right.
So this was the left call of the same recursive function.
So we know that we are over here.
Hence we can just make it manually the left of this particular node.
So that is going to be an O of one operation O of one time operation, which is more efficient.
That's why we are proceeding in this manner.
So let's go ahead and continue.
So we have five over here, and we have identified that two is going to be towards the left of five.
And that was part of this call zero three.
Right.
So let's proceed.
Now we are inside this call where we are having left as zero and right as three.
So we made a node and now we are going to process its left.
So this is the middle now right.
So this is the middle right.
So let me just write this over here.
This is the middle.
Now its left is going to be this part.
And its right is going to be this part.
So let's write that.
So we are going to make a call on the left where middle is this part.
So the left part at this point have has left as zero and right as middle minus one which is one, minus
one which is zero itself.
So left is going to be zero, and right also is going to be zero.
So we are going to have a call again for the same function with zero comma zero.
All right.
So at this point middle is again going to be calculated.
So when we calculate middle and let me just have a placeholder over here.
After we are done with the left part we are going to process the right part which is two comma three
right.
So left is going to be middle plus one which is two.
And right remains unchanged.
So let's write that over here which is two comma three.
So let's go ahead.
Now when we process the call with zero comma zero left and right both are going to point at index zero
right.
So left and right points at index zero and middle in that case is going to be also pointing at index
zero because left is pointing over here.
Right is also pointing over here.
So middle will be zero plus zero by two which is zero itself.
Right.
So we are getting this value one over here at the index middle.
So we are going to make a node out of it and insert it to the left of this particular node.
So we know that it's the left of this node because this was part of the left call.
Right.
This was the left call.
This is going to be the right call right.
So this again was the left call.
That's why we got this towards the left of this node.
And this is the right call.
All right.
So let's proceed now.
Middle is over here.
Middle is over here right.
So middle is at index zero.
Now we are going to process its left and then its right.
We can see both are empty right.
So we're going to just just get null and null over here.
Let's see why.
So again when we process its left all we're doing is we are keeping left as it is, which is zero.
And right is going to be middle minus one which is zero minus one.
So we are making a call with left as zero and right as minus one.
And this will be the base case of the recursive call.
That is, when left is greater than right we will just return null.
So that's going to be the base case.
So we hit the base case over here.
And this is just going to return null.
All right.
So that's how we get null as the left of this particular node over here.
Then we are going to process the right.
All right.
So this was the left of this.
Now again we are going to process its right.
So for this again we are going to leave right as it is.
And left is just going to be middle plus one which is going to be zero plus one because middle was zero.
So we are having a call with one comma zero.
That's the right call.
And that also is going to return because you can see left is greater than right.
And that's our base case.
So this will also return.
So over here also we get null.
All right.
So let's proceed.
Now we are done with this call.
So this now is going to be over.
This call is going to be over because we identified the node.
And then we did the left call and the right call.
And that's over.
Right.
So this is going to return.
Now we are going to have the right call.
So we are going to have the right call.
Now when we have the right call for this particular node we are going to use the indexes two and three.
So we have already seen the logic for that right.
So left is two and right is going to be three.
That is we are leaving right as it is.
And then we are changing left to middle plus one.
And middle was one at that instance.
So that's how we are getting two comma three.
And again we calculate the new middle value which is going to be two plus three by two.
And then we will floor it.
So we'll get two as the middle value at this instance.
So at index two we have this value.
So we make it a node.
And we're going to insert it to the right because this was a right call.
Right.
So we know that it's going to be the right.
So that's it again we proceed and we're going to check its left.
And its right now for its left we see we don't have anything right.
So its if the middle value at this point is two now left for its left.
We are just going to change right to middle minus one which is one.
So we're going to have a call where two comma one left is two and right is one, right is one because
that's two minus one.
Again this will just return null because you can see left is greater than right.
So that's why over here we are getting null and we proceed.
We are making the right call.
And for the right call what is what is the case that we are dealing with.
You can see we have four over here.
That is we are making a call with three comma three.
Right.
So we are leaving three as it is.
And left is changed to right middle plus one.
So middle is two two plus one is three.
So at this case left is also three.
Right is also three.
And then we find middle is three plus three by two which is three itself.
And that gives us this value over here.
So we make a node out of it.
And we are inserting it to the right of this particular node.
Now we again proceed.
We are going to check its left and its right.
Now that's just going to be null and null again.
Right.
Because we will see that left is greater than.
So it will return and we'll get null and null again.
So this part over here is going to return.
And then this is over.
So that was part of the left call.
All right.
So this was part of the left call for this particular node.
Now we are going to go ahead and process the right part.
So let's just clear this up.
So this part over here is done.
Now we are making the right call.
So let's just write it inside the call stack.
So the left now is going to be five.
And the right is going to point at index eight.
We calculate the new middle which is five plus eight divided by two.
So that's equal to 13 by two which is 6.5.
And when we floor it that's going to be equal to six.
So middle is pointing at index six.
So we are going to make a node out of this.
And this is going to be inserted towards the right of this node.
And we know that it's towards the right because this is a right call.
Right.
So this was the right call.
Right.
So we're going to insert this over here.
And then we proceed in the similar manner.
Again we are going to call the same function.
And we are going to process the left of the part left part.
And this is the left part which is five comma five.
And this is the right part which is eight comma nine.
Right.
So let's write that.
Let's just write that over here seven comma eight okay.
It's eight and nine are the values.
But the indices are seven and eight.
So the left call will have five comma five.
That is left is left.
Uh we are not changing the left index.
And right is going to be middle minus one which is six minus one.
That's how we get five over here.
Now when we have five comma five that's the left call.
Again middle is going to be equal to index five which is six.
So we make a node out of this.
And this is going to be inserted towards the left over here.
And then we process the right part where we have seven and eight.
So at that point middle is going to point towards index seven because seven plus eight by two.
And then when we floor it we'll get seven itself.
So this is the right call.
So that's why this node over here which is eight is going to be inserted towards the right over here.
So we have eight over here.
And then we are going to process the left and right of this right.
So in the left we're just going to return null because you can see we have nothing right.
So there is nothing over here.
So the left is going to be null.
And again you can see that we are getting nulled because left is going to be greater than right at this
point when we process it's left.
So middle is seven, and when we process it's left we don't change the left.
So left is seven itself and right is going to be middle minus one which is seven minus one which is
six.
So that's why you can see left is greater than right.
And it will return null.
So that's how we get null over here.
And then when we process its right left is going to be eight.
And right is going to be also eight right index eight.
So we have a call with eight comma eight.
So at this time we get middle also to be index eight.
And that's pointing to the value nine.
So we make a node out of this.
And this is going to be inserted towards the right over here.
And that's how we get nine over here.
So this is how we are going to solve this question in the recursive manner.
So let's just write this binary search tree in a neat manner over here.
So we have five then 2134768 and nine.
Now you can see that this is height balanced.
This binary search tree over here is height balanced.
So you can see for any subtree.
For example for this one the difference between the depth of the nodes right is not greater than one
right.
So these are this is a height balanced binary search tree.
Now let's also take a quick side note.
This algorithm would not have worked if in the question it was not mentioned that the values in the
array is strictly increasing.
Right.
So that's an interesting thing to notice about this algorithm, because it's given that the values are
strictly increasing.
That's why we know that the values are distinct.
Now if they were not distinct then the algorithm would not work.
Let's take an example.
Let's say the array was one, two, two, two and three.
Now in this case we would have found the middle as 01234.
The middle would be index two.
Right.
So we go ahead and make a node out of this.
And then when we process the left you can see that this value over here is two itself.
Right.
And this should not come to the left.
It won't be part of the left subtree of this particular root node.
So that is one reason why this is not going to be correct.
Our algorithm is not going to work.
And then you can see even if we insert all of these towards the right right.
It's not going to be height balanced.
You can have two and two over here and three over here and one over here.
So that it follows the binary search tree property.
But this is not going to be height balanced.
So the algorithm will not work if the values are not distinct.
So this is a good observation to make.
Now let's proceed and take a look at the time and space complexity of this solution.
Now the time complexity of this solution is going to be O of n, because we have to traverse through
each element of the given array, and then we have to make a node out of it.
Right.
So we have to make a node out of it.
And then we have to uh, go ahead and recursively call the same function for its left and its, its
particular right of the particular node where we are at.
So you can see we have to traverse through the elements, we have to make a node and at every element.
So basically you can think of it in this manner every element has to become the middle at some point
so that we can make a node out of it and insert it into a binary search tree.
So the time complexity over here is going to be O of n, and the space complexity is also going to be
O of n.
Why is that.
So that so now what are the things that take up space.
We will have to return the binary search tree.
And then we will also take up space on the call stack.
Now the binary search tree is going to have n elements.
So that's why the space of this binary search tree is going to be of the order of n.
But when it comes to the call stack we are going to have only calls, which is of the order of the height
of the binary search tree.
Right.
So we can say that the space used because of the call stack is going to be O of log n or O of the height
of the binary search tree.
Now, because this is a balanced, uh, height balanced binary binary search tree, we can say that
the height is going to be of the order of log n.
So the space taken up by the call stack is going to be of the order of log n.
But because this is greater than this.
So we can say that the space complexity of this solution is going to be o of n.