Welcome back.
Let's now go ahead and code the recursive solution, which we discussed in the previous video, where
we are given a sorted array which is strictly increasing.
And from this array we will create a binary search tree which is height balanced.
So let's go ahead and do this.
Now to start with I'm going to have a class node.
So using this class we will create each node.
And we'll have our constructor over here.
And to the constructor we will be passing the value.
And then inside over here we're just going to say this dot value is equal to the value which is passed
over here.
And we will say this dot left is equal to null.
And this dot right is equal to null.
So each node is going to have a value and a left and a right.
All right.
Now let's go ahead and write the function.
So let's call this function build BST.
From sorted array.
All right.
Now this function is going to take in the array.
So let's just call this array numb's.
And it's also going to take in the left index.
And the right index where we are at that particular instance.
That's because this is going to be a recursive function right.
So inside this function we will call this function again by varying the left and the right pointers.
So left initially is going to be equal to zero.
And right initially is going to be equal to numb's dot length minus one.
Now inside this function first let's write the base case.
So the base case is going to be when left is greater than right right.
So if left is greater than right.
In that case we can just return null.
So when this hits, we will be returning null.
So that place is going to be a null in the binary search tree.
All right.
Now let's proceed.
Now we go ahead and calculate middle in the array which is given to us which is numb's over here.
So let's say let middle is equal to math dot floor.
Left plus right divided by two.
And after identifying the middle value in the array at that particular call, we are going to create
a node out of this value.
So let's say const node is equal to new node.
So we are calling the constructor over here.
And then we will be passing this value which is the middle in the value at the index middle in the array
which is given to us.
So over here we are passing numb's at middle.
So using this value we create a node.
And then we are just going to go ahead and recursively call the same function to identify the left and
right positions for this particular node.
So we can say node dot left is equal to.
Again we call the same function build BST from sorted array.
And now we pass the array.
And because this is the left right this is node dot left.
So we don't change left.
Left is going to be as it is.
But right is going to be changed to middle minus one.
All right.
Now we're going to do the same thing for node dot right as well.
So node dot right is going to be the same function we call the function recursively.
And now because we are trying to find the right position.
So we're going to change left to middle plus one.
So this is going to be middle plus one.
And then right is not changing at all.
It's going to be right itself.
All right.
So that's it.
And then this will keep recursively calling the function till it hits the base case at which point it
will return null.
So finally after we are done with this after these return we will just return the node.
So that will be the head of the binary search, the root of the binary search tree.
All right.
So let's go ahead and call the function and test our code.
And let's say we are passing an array.
So one, two, three, four and five.
So this is the sorted array which is passed to it.
So let's go ahead and call this function.
And let's take a look at the output.
So we are getting three over here.
So let's try to draw the output so that we can visualize this.
So let me just grab a pen.
All right.
So over here you can see that the binary search tree has three over here which is the root.
Right.
So let's write three over here.
And let's open it up.
So you can see after this the left of this node is one and the right is four.
So let's write this over here.
So the left over here is one and the right is node four.
And then if we open this up let's open this also.
So we get the left of this node over here is going to be null.
So this is null.
And the right is going to be a node with value two.
So this is two over here.
Now if we open this up it's just going to be null and null.
All right.
So that's correct.
Now let's open this part as well.
So four is having the left node as null and the right node as five.
So this is null.
And this is five.
Now if we open up five, we will just get null and null.
Yes.
That's correct.
So this is how the binary search tree looks like.
So you can see yes, this is a binary search tree because the binary search tree property is fulfilled.
So everything to the right of three is less than three.
And everything sorry, everything to the left of three is less than three, and everything to the right
of three is greater than three.
So we can see that the binary search tree is fulfilled.
And that's also true with each of these nodes.
Right?
So whatever is right of one is greater than one.
Whatever is right of four is greater than four.
So yes, this is how the binary search tree looks.
And we can see that it is height balanced.
Right.
So the height of these two subtrees are the same.
Right.
And the height over here differs by one because this is over here null.
And we have a node over here.
So yes this is a height balanced binary search tree.
And it's working.
Now let's try to run through the code and understand how this is working.
So we'll take the same input.
So let's just clear this up over here.
And the array which is passed to us is one, two, three, four, five.
And we are calling the build binary search tree from sorted array function and left at this point is
equal to zero and right is equal to the length minus one.
The length over here is five.
So right is equal to four.
So let's track our call stack over here.
So this is the call with zero and four.
All right.
So left is zero and right is four.
Now let's go ahead and see what's happening over here.
So left is zero.
Right is four.
And we see that left is not greater than right.
So we continue and we are calculating middle.
Middle is left plus right by two.
So that's equal to two at this point.
Now let's write the indices over here 0123 and four.
All right.
So at index two we have the value three.
So we are going ahead and making a node with this value which is three.
So let's write the node over here.
So this is our node with value three.
And then we are saying node dot left.
That is whatever should come over here is what we get back from this function called over here.
Now let's take a look at this function call over here.
At this point left is not changing.
So left is still zero and right is going to be middle minus one.
And middle is equal to two.
So right is equal to one.
So we are making a call and the left index is zero.
And the right index is one.
All right.
So this is the call for node dot left.
Now let me just have a placeholder over here for node dot right.
So when we call node dot right.
When we try to find node dot right.
That is whatever comes over here.
We are going to pass the left index as middle plus one which is two plus one which is three.
And right is not going to change which is four itself.
All right.
So let's have a placeholder for that.
So that's going to be three comma four.
So we'll come back to this.
Now let's proceed.
Now we are in the call zero one.
So let's just clear this up a little bit.
And we are again inside the build BSD from sorted array function, and we are trying to find out what
should come over here.
Now we are inside.
This left is equal to zero and right is equal to one.
Left is not greater than right.
So we come over here and we calculate middle which is going to be zero plus one divided by two.
And then we are floating it right.
So that's going to be equal to zero.
So middle is equal to zero.
So that's this index over here.
So we make a node out of this right.
We make a node out of this.
And that's going to be this node over here.
Right.
So this is going to be the node with value one.
So that's this node.
All right.
And over here you can see that we are returning this particular node.
Right.
So we are returning this node.
That means in this call it's going to return this node over here.
All right.
And we have seen that that was for this position.
So when we get to this line we will fill this node to this place.
But before we get to this we are going to start first to identify what is to be made to the left and
right of this particular node.
So let's go ahead and do that.
So I'm just writing this over here so that we can keep track of the recursive call and how it works.
So let's continue.
So we have made a node out of this value which is one.
And then we are calling node dot left to identify what should be to the left of this.
So and then later we will call node dot right to identify what should be the to the right of this.
So that's how this works.
So for this call node dot left we are again leaving left as it is which is zero itself.
And right is going to be middle minus one.
And middle is equal to zero right.
So right is going to be minus one zero minus one is minus one.
So when we come inside that call right.
So zero minus one.
Let me just write this over here zero minus one.
When we come inside that call left is going to be greater than right because zero is greater than minus
one.
So we are going to return null.
So that means over here we are going to have null.
And this returns.
All right.
So later we come to this part where we are going to call node dot right.
To identify what should come over here.
At this point we are going to make left middle plus one.
And middle was zero right.
So that's going to be one.
And right is not going to change at all.
So right is one itself.
All right.
So we have one and one and we are inside the call.
So let's write that over here in our call stack.
Again we have a call with one comma one at this point.
And middle is going to be one plus one divided by two which is one itself.
So let's just clear this up a little bit.
All right, so we have one and one over here.
And middle is going to be one, and we are going to make a note out of what is there at index one,
which is two.
All right.
And that two is going to be returned at this point.
So we are making the node with value two over here.
And then it's going to be returned.
So it's going to be positioned over here.
Right.
And you can see over here these two are going to return null right.
Because why is that.
So it's left and it's light right are going to be null.
So this is null and this is null.
Why is that so.
Because left is going to be greater than right in these instances.
So we have one and one at this point.
Now left is left unchanged.
And right is going to be middle minus one which is zero.
So we have one comma zero.
So left is greater than right.
So this returns and we have null over here.
Similarly over here we are going to increment left.
So left is going to be middle plus one middle plus one.
So left is going to be two and right is left as it is which is one itself.
So again when we come inside the function two is greater than one.
So that's why this part also is going to be null.
So this is also null.
This is also null.
So this is this has been formed.
And then we come over here and we have seen that that's what is going to happen over here.
Right.
We created one.
And then we go deeper to identify its left and right.
And at this point we again go deeper to identify its and its left and its right.
Now these all have returned.
So we come over here and now this node over here is going to return to this part.
So we are going to place this over here.
So one is coming over here.
And this is already constructed right.
So this is null.
And over here we have two.
And over here we have null.
All right.
So this has returned.
So this was this part right where we created the node one.
All right.
So that was part of this call where we passed zero as the left index and one as the right index.
Now that was part of node dot left right the left of this index.
So this part over here is done.
Now we come to this line.
Let me just change the color of the pen.
We come over here and we identify node dot right.
That is what is it that should come over here.
And for this we are passing three comma four.
So let's just clear this up a little bit.
So left is passed as three and right is passed as four.
All right.
So left is three and right is four.
Now we come over here.
Left is is left greater than three for right.
No three is not greater than four.
So we continue and we go ahead and identify the middle value which is three plus four divided by two.
And then we have flooring it.
So we will get three itself as the middle value.
And this is zero.
This is one this is two this is three this is four.
So at index three we have the value four.
So we are going to make a node out of it right.
So this is going to be node four.
And then we will return this at this line.
So it will come and sit over here.
But before that we will identify its left and its right in these parts.
So its left.
Let's go ahead over here.
Let's see what's happening over here.
Let me just clear this up also.
So in our call stack we just have this call which is three comma four.
So let's write that over here.
And we have seen that this will return the node four once it's back.
All right.
So we're going deeper.
First we are calling node dot left to identify what should come in this place.
And left is left as it is.
So we have three itself.
And right is going to be middle minus one.
And middle is equal to three right.
So middle minus one is going to be two.
Now three comma two you can see left is greater than right.
So it's going to return null when we come over here.
Right.
So left is greater than null greater than right.
So this part over here is going to be null.
All right.
So then we continue we come to this line and we identify its right which is going to be again a recursive
call.
So this has returned null.
So I'm just crossing it out.
So we are over here.
Now at this point we are calling the function again recursively.
And left is going to be middle plus one which is three plus one which is four.
And right is going to be right itself which is four.
So we are calling the function recursively with four comma four.
So we come over here four is not greater than four.
So we continue and we are calculating the new middle.
So at this point it's four comma four.
So four plus four by two.
That gives us four itself.
And at index four we have the value five.
So we are going to make a node out of this.
And that's going to be placed over here.
Right.
So that is when it is returned.
But again before that we identify its left and its right which is going to be null and null.
Right?
Why is that so?
Because we have four and four at this moment.
So when we call no dot left to identify what should come over here, left is going to be four, but
right is going to be four minus one which is three.
So you can see four is greater than three.
So that's why it returns at this place.
And hence we have null over here.
Now when we come to no dot right we're going to pass middle plus one as left which is four plus one
which is five and right is left as it is.
So we have five and four again when we come inside over here we see that five is greater than four and
it returns null.
So this part over here is also null.
So once this is done we're going to return this particular node which is five.
And that is the right that was part of the node dot right called for this particular node.
Right.
So that's it.
So this call over here will return.
Now node dot left and node dot right.
For this particular node is done which is the node that we made over here with the value four.
Right with the value four.
And then it's going to return.
That means this operation over here which we made a placeholder for is going to be executed.
And this four is going to be placed over here.
So we have four over here.
And towards its left we have null.
And for its right we have five, and for the left and right of five we have null.
So this is how the function works.
So let's just write this in a clean manner over here once more.
So let's take a look at how the binary search tree looks like.
Right.
So uh, so we have three over here at the root.
It is.
Clear this up.
And write it in a neat manner.
So we have three over here and then towards its left we have one towards its right we have four.
And then for one it only has something towards this right which is two.
And for four we only have something towards its right which is five.
So this is how our binary search tree looks like.
And we can see that it is following the binary search tree property.
And it is height balanced.
So yes it's working.
So our code is working.
Now what about the space and time complexity of this solution?
The time complexity of this solution is going to be O of N, because we have to go through each element
in the array which is given to us and make it a node and do some constant time operations.
Right.
So we have to traverse through the array.
So that's why for each instance and after while we traverse the array for each instance, we have to
do some constant time operations like making a node.
And then we go ahead and return the node.
Right.
So we have already accounted for these as traversing the array.
So that's why the time complexity is going to be O of n.
And what about the space complexity.
The space complexity of this solution is going to be of the order of the height or the maximum depth
of the binary search tree.
All right.
However, you can also say that there is space consumed because we are returning the binary search tree,
right?
We are building the binary search tree.
So for that, the space complexity is going to be O of n, because in the binary search tree there is
going to be n elements.
So the call stack is going to take O of log n space.
But then n is greater than log n.
So we can say that the space complexity of this solution is o of n.