Hi everyone, let's do this question.
You are given an array where the elements are strictly in increasing or ascending order.
Convert it to a height balanced binary search tree.
A height balanced binary tree is a binary tree in which the depth of the two subtrees of every node
does not differ by more than one.
So this is a question which is given to us.
So we have to convert a sorted array to a binary search tree.
Now let's say the array which is given to us is 12345.
Now we have to convert this to a height balanced binary search tree.
So that's the question.
Now over here it's mentioned that a height balanced binary tree is one in which the depth of the two
subtrees of every node does not differ by more than one.
So this is what we have to ensure.
And it's also given that the array which is given to us is strictly increasing.
So that means that we cannot have equal elements.
For example we cannot have three comma three comma five.
So that would not be strictly increasing.
So that's the question over here.
Now let's go ahead and write a few test cases.
Remember in the interview you can always ask the interviewer if he or she is okay with coming up with
test cases together.
Right.
So that would be a good practice because you can be sure that you have a good understanding of what
the expectation is.
So over here, let's now go ahead and write a few test cases.
If this is the array which is given to us, we can convert it into a binary search tree in this manner.
Right.
You can see that this is a valid binary search tree because it follows the binary search tree property.
Or everything towards the right is greater than whatever is there in that particular node.
Right?
So you have one over here and everything to its right is greater than one.
So you have two over here, everything to its right is greater than two etc..
So it's following the binary search tree property.
But we can notice that this is not height balanced right.
This tree over here is not height balanced.
So you have no node towards its left.
And then the depth of this node over here is going to be four.
Right.
Because you have one, two, three, four four edges from the root to this particular node over here.
So the left and right over here is not differing by one node.
Right.
So four -0 is four.
So we can see that this tree over here is not height balanced.
So if the array which is given to us is this one over here, we can convert it into a binary search
tree which is height balanced in multiple ways, some of which are these.
Right.
For example, we can have three over here and four and five over here, and two and one over here.
You can see every node is following the binary search tree property.
For example, whatever is towards the left of this node is less than two right.
And towards its right there is nothing.
And for the node three, everything in its left is less than three, and everything in its right is
greater than three.
So you can see the binary search tree property is followed over here.
And this is height balanced.
Right.
So you can see this node over here has a depth of two.
And this node over here also has a depth of two.
Now when it comes to the two sides of this particular node this side has this node over here right.
So there is one edge over here.
And there is zero edges over here.
So yes the difference is only one.
So we can see that this tree over here is height balanced.
Similarly these two are also height balanced.
And they are following the binary search tree property.
So we can have multiple solutions.
We just need to write an algorithm to come up with any one of these possibilities.
Now if the array which is given to us is seven comma nine, we can have two possibilities, right?
We can have seven and then we towards its right we can have nine, or we can have nine at the root and
towards its left we can have seven.
So there are these two possibilities.
So over here we have taken care.
We have taken a look at few test cases.
And we have noticed that multiple solutions are possible.
The only two conditions is that it should be a valid binary search tree, and it should be height balanced.
Now in the next video, let's try to think how we can solve this question.