1
00:00:00,620 --> 00:00:02,960
Hi everyone, let's do this question.

2
00:00:02,960 --> 00:00:07,520
You are given an array where the elements are strictly in increasing or ascending order.

3
00:00:07,520 --> 00:00:10,550
Convert it to a height balanced binary search tree.

4
00:00:10,580 --> 00:00:15,950
A height balanced binary tree is a binary tree in which the depth of the two subtrees of every node

5
00:00:15,950 --> 00:00:17,960
does not differ by more than one.

6
00:00:17,960 --> 00:00:19,820
So this is a question which is given to us.

7
00:00:19,820 --> 00:00:22,970
So we have to convert a sorted array to a binary search tree.

8
00:00:22,970 --> 00:00:26,000
Now let's say the array which is given to us is 12345.

9
00:00:26,000 --> 00:00:30,110
Now we have to convert this to a height balanced binary search tree.

10
00:00:30,110 --> 00:00:31,220
So that's the question.

11
00:00:31,220 --> 00:00:37,610
Now over here it's mentioned that a height balanced binary tree is one in which the depth of the two

12
00:00:37,610 --> 00:00:40,880
subtrees of every node does not differ by more than one.

13
00:00:40,880 --> 00:00:43,010
So this is what we have to ensure.

14
00:00:43,010 --> 00:00:47,570
And it's also given that the array which is given to us is strictly increasing.

15
00:00:47,570 --> 00:00:49,610
So that means that we cannot have equal elements.

16
00:00:49,610 --> 00:00:52,190
For example we cannot have three comma three comma five.

17
00:00:52,190 --> 00:00:54,290
So that would not be strictly increasing.

18
00:00:54,290 --> 00:00:55,670
So that's the question over here.

19
00:00:55,670 --> 00:00:58,190
Now let's go ahead and write a few test cases.

20
00:00:58,190 --> 00:01:03,350
Remember in the interview you can always ask the interviewer if he or she is okay with coming up with

21
00:01:03,350 --> 00:01:04,340
test cases together.

22
00:01:04,340 --> 00:01:04,490
Right.

23
00:01:04,490 --> 00:01:08,660
So that would be a good practice because you can be sure that you have a good understanding of what

24
00:01:08,660 --> 00:01:09,740
the expectation is.

25
00:01:09,740 --> 00:01:12,980
So over here, let's now go ahead and write a few test cases.

26
00:01:12,980 --> 00:01:18,080
If this is the array which is given to us, we can convert it into a binary search tree in this manner.

27
00:01:18,080 --> 00:01:18,350
Right.

28
00:01:18,350 --> 00:01:23,720
You can see that this is a valid binary search tree because it follows the binary search tree property.

29
00:01:23,720 --> 00:01:28,160
Or everything towards the right is greater than whatever is there in that particular node.

30
00:01:28,160 --> 00:01:28,310
Right?

31
00:01:28,310 --> 00:01:31,550
So you have one over here and everything to its right is greater than one.

32
00:01:31,550 --> 00:01:34,730
So you have two over here, everything to its right is greater than two etc..

33
00:01:34,730 --> 00:01:37,370
So it's following the binary search tree property.

34
00:01:37,370 --> 00:01:40,400
But we can notice that this is not height balanced right.

35
00:01:40,400 --> 00:01:42,770
This tree over here is not height balanced.

36
00:01:42,770 --> 00:01:45,110
So you have no node towards its left.

37
00:01:45,110 --> 00:01:49,400
And then the depth of this node over here is going to be four.

38
00:01:49,400 --> 00:01:49,550
Right.

39
00:01:49,550 --> 00:01:54,500
Because you have one, two, three, four four edges from the root to this particular node over here.

40
00:01:54,500 --> 00:01:58,610
So the left and right over here is not differing by one node.

41
00:01:58,610 --> 00:01:58,880
Right.

42
00:01:58,880 --> 00:02:01,100
So four -0 is four.

43
00:02:01,100 --> 00:02:04,010
So we can see that this tree over here is not height balanced.

44
00:02:04,010 --> 00:02:09,290
So if the array which is given to us is this one over here, we can convert it into a binary search

45
00:02:09,290 --> 00:02:12,800
tree which is height balanced in multiple ways, some of which are these.

46
00:02:12,800 --> 00:02:13,010
Right.

47
00:02:13,010 --> 00:02:17,510
For example, we can have three over here and four and five over here, and two and one over here.

48
00:02:17,510 --> 00:02:21,260
You can see every node is following the binary search tree property.

49
00:02:21,260 --> 00:02:25,850
For example, whatever is towards the left of this node is less than two right.

50
00:02:25,850 --> 00:02:28,460
And towards its right there is nothing.

51
00:02:28,460 --> 00:02:34,340
And for the node three, everything in its left is less than three, and everything in its right is

52
00:02:34,340 --> 00:02:35,060
greater than three.

53
00:02:35,060 --> 00:02:38,840
So you can see the binary search tree property is followed over here.

54
00:02:38,840 --> 00:02:40,130
And this is height balanced.

55
00:02:40,130 --> 00:02:40,340
Right.

56
00:02:40,340 --> 00:02:43,370
So you can see this node over here has a depth of two.

57
00:02:43,370 --> 00:02:45,830
And this node over here also has a depth of two.

58
00:02:45,830 --> 00:02:52,010
Now when it comes to the two sides of this particular node this side has this node over here right.

59
00:02:52,010 --> 00:02:53,270
So there is one edge over here.

60
00:02:53,270 --> 00:02:54,710
And there is zero edges over here.

61
00:02:54,710 --> 00:02:56,300
So yes the difference is only one.

62
00:02:56,300 --> 00:02:58,670
So we can see that this tree over here is height balanced.

63
00:02:58,670 --> 00:03:01,370
Similarly these two are also height balanced.

64
00:03:01,370 --> 00:03:03,830
And they are following the binary search tree property.

65
00:03:03,830 --> 00:03:05,570
So we can have multiple solutions.

66
00:03:05,570 --> 00:03:09,290
We just need to write an algorithm to come up with any one of these possibilities.

67
00:03:09,320 --> 00:03:14,150
Now if the array which is given to us is seven comma nine, we can have two possibilities, right?

68
00:03:14,150 --> 00:03:20,060
We can have seven and then we towards its right we can have nine, or we can have nine at the root and

69
00:03:20,060 --> 00:03:21,860
towards its left we can have seven.

70
00:03:21,860 --> 00:03:23,930
So there are these two possibilities.

71
00:03:23,930 --> 00:03:26,120
So over here we have taken care.

72
00:03:26,120 --> 00:03:28,070
We have taken a look at few test cases.

73
00:03:28,070 --> 00:03:30,890
And we have noticed that multiple solutions are possible.

74
00:03:30,890 --> 00:03:36,260
The only two conditions is that it should be a valid binary search tree, and it should be height balanced.

75
00:03:36,290 --> 00:03:39,800
Now in the next video, let's try to think how we can solve this question.