1
00:00:00,810 --> 00:00:01,830
Hi everyone.

2
00:00:01,830 --> 00:00:08,550
If you have a balanced binary tree, the height of that tree can be obtained by doing the floor of log

3
00:00:08,550 --> 00:00:12,240
n, where n is the number of nodes in the balanced binary tree.

4
00:00:12,270 --> 00:00:14,340
Now let's discuss the proof for this.

5
00:00:14,340 --> 00:00:16,920
Now this is going to be divided into two parts.

6
00:00:16,920 --> 00:00:23,340
In the first part, we will prove that when you take log n plus one again n is the number of nodes that

7
00:00:23,340 --> 00:00:26,370
would be less than or equal to the height plus one.

8
00:00:26,370 --> 00:00:33,240
Now if this is true now because this over here is less than or equal to h plus one the ceiling, or

9
00:00:33,240 --> 00:00:38,490
when we round this up, we can say that we will get this to be equal to h plus one.

10
00:00:38,490 --> 00:00:44,940
And then when we take this one to the left hand side, this becomes that ceiling of log n plus one minus

11
00:00:44,940 --> 00:00:46,380
one is equal to h.

12
00:00:46,380 --> 00:00:48,780
Now this is going to be part one of the proof.

13
00:00:48,780 --> 00:00:50,910
Again I'm just outlining the steps over here.

14
00:00:50,910 --> 00:00:52,620
And then we will see this in detail.

15
00:00:52,620 --> 00:00:59,700
Now in part two we will prove that this part over here that is ceiling of log n plus one is equal to

16
00:00:59,700 --> 00:01:02,670
log of floor of log n plus one.

17
00:01:02,670 --> 00:01:08,190
Now if this is true, if we prove this we will substitute this part over here over here in the equation.

18
00:01:08,190 --> 00:01:13,260
Now that would give us floor log n plus one minus one is equal to h.

19
00:01:13,260 --> 00:01:20,280
And this minus one and this plus one will cancel out and it will leave us with floor of log n is equal

20
00:01:20,280 --> 00:01:20,880
to h.

21
00:01:20,880 --> 00:01:22,620
And that is what we want to prove.

22
00:01:22,620 --> 00:01:22,860
Right.

23
00:01:22,860 --> 00:01:24,360
So that is what we have over here.

24
00:01:24,360 --> 00:01:26,910
Again let me repeat the height of a binary tree.

25
00:01:26,910 --> 00:01:31,140
A balanced binary tree can be obtained as floor of log n.

26
00:01:31,140 --> 00:01:32,460
Now let's proceed.

27
00:01:32,700 --> 00:01:37,920
First we are going to start with the first part over here which is log n plus one is less than or equal

28
00:01:37,920 --> 00:01:38,880
to h plus one.

29
00:01:38,880 --> 00:01:44,430
And then from this we will derive that ceiling of log n plus one minus one is equal to h.

30
00:01:44,430 --> 00:01:47,400
Now over here we have a balanced binary tree.

31
00:01:47,430 --> 00:01:50,130
Now let's take a look at the number of nodes.

32
00:01:50,130 --> 00:01:52,860
Over here we can see that we have one node.

33
00:01:53,530 --> 00:01:56,560
Now in this level we have two nodes.

34
00:01:56,560 --> 00:01:59,680
Similarly over here we have four nodes.

35
00:01:59,680 --> 00:02:04,150
And in this level over here we can have a maximum of eight nodes.

36
00:02:04,150 --> 00:02:04,360
Right.

37
00:02:04,360 --> 00:02:08,620
So even if each of these four nodes has two children that's eight nodes.

38
00:02:08,620 --> 00:02:09,850
So this is the maximum.

39
00:02:09,850 --> 00:02:16,270
Now if you take a look at this pattern over here it's one plus two plus four plus eight etc. up to two

40
00:02:16,300 --> 00:02:18,460
to the power h where h is the height.

41
00:02:18,460 --> 00:02:18,790
Right.

42
00:02:18,790 --> 00:02:24,730
So if the tree had just one node then the height is equal to zero and two to the power zero is equal

43
00:02:24,730 --> 00:02:25,150
to one.

44
00:02:25,150 --> 00:02:28,210
But if the height of the tree is equal to one, right?

45
00:02:28,210 --> 00:02:30,580
So that would be something looking like this.

46
00:02:30,580 --> 00:02:33,700
Now in that case over here we have two to the power one nodes.

47
00:02:33,700 --> 00:02:38,680
So that's why we can say that in the last level we will have two to the power h nodes.

48
00:02:38,680 --> 00:02:39,070
All right.

49
00:02:39,100 --> 00:02:44,440
Now when you take a look at this this is going to be just a geometric progression right where you are

50
00:02:44,440 --> 00:02:46,150
always multiplying with two.

51
00:02:46,180 --> 00:02:49,180
So one into two gives you two, two into two gives you four.

52
00:02:49,180 --> 00:02:50,740
And it goes on in this manner.

53
00:02:50,740 --> 00:02:58,060
Now for a geometric progression we know that sum up to n terms is equal to a into r to the power n minus

54
00:02:58,060 --> 00:03:01,660
one by r minus one, where this is the geometric progression.

55
00:03:01,660 --> 00:03:06,820
So the first term is a and then we're just keeping on multiplying with r to get the remaining terms.

56
00:03:06,820 --> 00:03:09,430
Now let's make use of this formula over here.

57
00:03:09,430 --> 00:03:11,800
Now we can see that the first term is one.

58
00:03:11,800 --> 00:03:15,520
And the number with which you are multiplying is equal to two.

59
00:03:15,550 --> 00:03:22,900
So we can see that this sum over here is equal to one into two to the power h plus one minus one by

60
00:03:22,900 --> 00:03:23,770
two minus one.

61
00:03:23,770 --> 00:03:25,360
Now r is equal to two.

62
00:03:25,360 --> 00:03:27,040
That's why we have two minus one over here.

63
00:03:27,040 --> 00:03:29,560
And then n is equal to h plus one.

64
00:03:29,560 --> 00:03:29,770
Right.

65
00:03:29,770 --> 00:03:30,700
So notice over here.

66
00:03:32,090 --> 00:03:36,080
So whatever is over here is one greater than what we have over here.

67
00:03:36,080 --> 00:03:37,550
So over here we have h.

68
00:03:37,550 --> 00:03:39,830
Hence we have h plus one over here.

69
00:03:39,830 --> 00:03:40,190
All right.

70
00:03:40,190 --> 00:03:45,590
So this is simplifying to two to the power h plus one minus one because the denominator becomes just

71
00:03:45,590 --> 00:03:46,160
one.

72
00:03:46,160 --> 00:03:46,670
All right.

73
00:03:46,670 --> 00:03:49,250
So let's make some space over here.

74
00:03:49,250 --> 00:03:55,730
So far we have seen that one plus two plus four plus etc. up to two to the power H is equal to two to

75
00:03:55,730 --> 00:03:57,890
the power h plus one minus one.

76
00:03:58,460 --> 00:04:05,000
Now in the case of the balanced binary tree, this expression over here is the maximum number of nodes,

77
00:04:05,000 --> 00:04:05,210
right?

78
00:04:05,210 --> 00:04:07,220
So why is this the maximum number of nodes.

79
00:04:07,220 --> 00:04:12,470
It's the maximum because it's not necessary that the last level is completely full right.

80
00:04:12,470 --> 00:04:16,160
So that's why we are not sure that we'll have two to the power H nodes over here.

81
00:04:16,160 --> 00:04:16,550
All right.

82
00:04:16,550 --> 00:04:22,580
So if n is the number of nodes that we have, then we can say that the number of nodes is less than

83
00:04:22,580 --> 00:04:24,470
or equal to this much.

84
00:04:24,470 --> 00:04:29,750
And we have already proved that the left hand side over here can be written as two to the power h plus

85
00:04:29,750 --> 00:04:30,980
one minus one.

86
00:04:30,980 --> 00:04:36,080
Therefore, we can say that n less than or equal to two to the power h plus one minus one.

87
00:04:36,080 --> 00:04:36,530
All right.

88
00:04:36,530 --> 00:04:38,060
Where n is the number of nodes.

89
00:04:38,060 --> 00:04:39,920
Again why is this less than or equal to.

90
00:04:39,950 --> 00:04:42,560
It will be equal to when the tree is completely full.

91
00:04:42,560 --> 00:04:48,140
But if the tree is something like this where you can see the last level is not full, then it would

92
00:04:48,140 --> 00:04:50,690
be less than two to the power x plus one minus one.

93
00:04:50,690 --> 00:04:51,950
All right, so let's proceed.

94
00:04:51,950 --> 00:04:57,980
Now we have established that n less than or equal to two to the power h plus one minus one.

95
00:04:59,210 --> 00:05:05,030
Now let's take this minus one to the left hand side and apply log on both sides.

96
00:05:05,030 --> 00:05:09,800
Then we get log of n plus one less than or equal to h plus one.

97
00:05:09,800 --> 00:05:11,990
Now again how do we go from here to here.

98
00:05:11,990 --> 00:05:14,360
Log of two to the power x.

99
00:05:14,360 --> 00:05:16,160
And the base over here is two itself.

100
00:05:16,160 --> 00:05:17,690
That's equal to x itself.

101
00:05:17,690 --> 00:05:18,050
All right.

102
00:05:18,050 --> 00:05:20,750
So this is this is something that's true again why is that.

103
00:05:20,750 --> 00:05:24,680
So remember log of eight is equal to three.

104
00:05:24,680 --> 00:05:26,090
And this three over here.

105
00:05:26,090 --> 00:05:28,940
If if instead of eight you write two to the power three.

106
00:05:28,940 --> 00:05:31,700
So this would be log of two to the power three.

107
00:05:31,700 --> 00:05:33,500
And you can see this is equal to three.

108
00:05:33,500 --> 00:05:36,590
So that's why log of two to the power x is x itself.

109
00:05:36,590 --> 00:05:42,020
And hence when we applied log on both sides on the right hand side we are getting the power which is

110
00:05:42,020 --> 00:05:43,190
x plus one over here.

111
00:05:43,190 --> 00:05:43,820
All right.

112
00:05:43,820 --> 00:05:44,780
So let's proceed.

113
00:05:44,780 --> 00:05:46,460
Let me make some space over here.

114
00:05:46,460 --> 00:05:51,050
Now we have that log of n plus one less than or equal to x plus one.

115
00:05:51,050 --> 00:05:54,350
Now let me take this one to the left hand side.

116
00:05:54,350 --> 00:05:54,740
All right.

117
00:05:54,740 --> 00:05:59,390
So when you do that you can see you get log of n plus one minus one.

118
00:05:59,390 --> 00:05:59,630
All right.

119
00:05:59,630 --> 00:06:00,890
So this one is what we took.

120
00:06:00,890 --> 00:06:03,890
The left hand side minus one less than or equal to h.

121
00:06:03,890 --> 00:06:07,580
Now the maximum value that this can take is equal to h.

122
00:06:07,580 --> 00:06:07,790
Right.

123
00:06:07,790 --> 00:06:13,220
So that's why we can say sealing or rounding up this value over here will give us h.

124
00:06:13,220 --> 00:06:17,180
So ceiling of log of n plus one minus one is equal to h.

125
00:06:17,180 --> 00:06:19,550
And hence we have proved the first part.

126
00:06:19,550 --> 00:06:20,030
All right.

127
00:06:20,030 --> 00:06:24,320
So we have got that ceiling of log n plus one minus one is equal to h.

128
00:06:24,320 --> 00:06:26,450
Now let's proceed to the second part.

129
00:06:26,450 --> 00:06:26,720
All right.

130
00:06:26,720 --> 00:06:28,370
Which is what we have over here.

131
00:06:28,370 --> 00:06:31,970
Now let's say m is equal to floor of log n.

132
00:06:32,910 --> 00:06:38,130
If this is true, then m less than or equal to log n less than m plus one.

133
00:06:38,130 --> 00:06:39,240
Now why is that so?

134
00:06:39,240 --> 00:06:41,430
Because over here we are flooring it right.

135
00:06:41,430 --> 00:06:43,410
So let's say n is equal to eight.

136
00:06:43,410 --> 00:06:46,650
In that case log eight is equal to three.

137
00:06:46,650 --> 00:06:49,500
So that's why m is equal to log n.

138
00:06:49,500 --> 00:06:52,620
In this case again m is what we are getting by flooring it.

139
00:06:52,620 --> 00:06:54,810
And if you floor three you will get again three.

140
00:06:54,810 --> 00:06:56,490
So that's why you have the equal to over here.

141
00:06:56,490 --> 00:07:01,860
But then if let's say n was nine, in this case we would get three point something.

142
00:07:01,860 --> 00:07:06,750
And then you can see it's actually greater than three which is the value that we get when we floor this.

143
00:07:06,750 --> 00:07:09,750
So that's why we have m less than or equal to log n.

144
00:07:09,750 --> 00:07:13,770
And then this would be less than m plus one which in this case would be four.

145
00:07:13,770 --> 00:07:14,100
Right.

146
00:07:14,100 --> 00:07:16,800
So this value over here is a decimal between 3 and 4.

147
00:07:16,800 --> 00:07:20,700
So we have m less than or equal to log n less than m plus one.

148
00:07:20,700 --> 00:07:22,290
Now let me clear this up.

149
00:07:23,750 --> 00:07:27,500
Now let's take two to the power these values.

150
00:07:27,500 --> 00:07:27,890
All right.

151
00:07:27,890 --> 00:07:32,810
So we're going to take two to the power M two to the power log N and two to the power M plus one.

152
00:07:32,810 --> 00:07:35,030
And the same relation would be maintained.

153
00:07:35,030 --> 00:07:40,190
So we have two to the power m less than or equal to n less than two to the power m plus one.

154
00:07:40,190 --> 00:07:45,710
Again remember log n when you do two to the power log n that's equal to n itself.

155
00:07:45,710 --> 00:07:46,040
All right.

156
00:07:46,040 --> 00:07:46,760
So why is that.

157
00:07:46,760 --> 00:07:50,090
So let's take an example two to the power log eight.

158
00:07:50,090 --> 00:07:52,160
And we know log eight is equal to three.

159
00:07:52,160 --> 00:07:55,670
So this over here is two to the power three which is eight itself.

160
00:07:55,670 --> 00:07:57,950
So you can see you have eight over here and here.

161
00:07:57,950 --> 00:08:01,640
So that's why two to the power log n is n itself.

162
00:08:01,640 --> 00:08:03,170
Hence we have n over here.

163
00:08:03,170 --> 00:08:04,850
Now let me clear this up.

164
00:08:04,850 --> 00:08:10,790
So we've we've got that two to the power M less than or equal to n less than two to the power n plus

165
00:08:10,790 --> 00:08:11,300
one.

166
00:08:11,300 --> 00:08:18,590
Now if I increase the value of n by one, I can get two to the power m less than n plus one less than

167
00:08:18,590 --> 00:08:20,630
or equal to two to the power n plus one.

168
00:08:20,630 --> 00:08:25,700
So this less than or equal to is now less than because I increase the value over here.

169
00:08:25,700 --> 00:08:29,480
And then over here, I have less than or equal to because I increase this value.

170
00:08:29,480 --> 00:08:31,100
This was previously less than.

171
00:08:31,100 --> 00:08:32,840
Now again let's take an example.

172
00:08:32,840 --> 00:08:34,430
Let's say n was eight.

173
00:08:35,160 --> 00:08:38,340
In that case, M is equal to three right and two to the power.

174
00:08:38,340 --> 00:08:39,810
Three is eight itself.

175
00:08:39,840 --> 00:08:44,550
Now if you increase this eight by one, this was over here less than or equal to right.

176
00:08:44,580 --> 00:08:49,380
Now when you increase this by one you can see it's definitely greater than what we have over here.

177
00:08:49,380 --> 00:08:51,450
So that's why we have less than over here.

178
00:08:51,450 --> 00:08:53,580
You can also think of it in this manner.

179
00:08:53,580 --> 00:08:58,260
In the best possible scenario n would have been equal to two to the power M right.

180
00:08:58,260 --> 00:09:03,330
It's it's again two to the power M cannot be greater than n because over here it's less than because

181
00:09:03,330 --> 00:09:04,920
of the way the sign points.

182
00:09:05,670 --> 00:09:09,570
So even if two to the power m is equal to n in that case.

183
00:09:09,570 --> 00:09:12,390
Also, if you increase n by one, it would be less than.

184
00:09:12,420 --> 00:09:14,160
So that's why we have less than over here.

185
00:09:14,160 --> 00:09:17,970
And then we are increasing the value of n to n plus one.

186
00:09:17,970 --> 00:09:19,290
So over here it was less than.

187
00:09:19,290 --> 00:09:21,660
And this becomes less than or equal to.

188
00:09:21,660 --> 00:09:25,470
Now again let's apply log across these three.

189
00:09:25,470 --> 00:09:25,890
All right.

190
00:09:25,890 --> 00:09:29,760
So over here we will get m over here we will get log n plus one.

191
00:09:29,760 --> 00:09:31,770
And over here we will get m plus one.

192
00:09:31,770 --> 00:09:36,390
So m less than log N plus one less than or equal to m plus one.

193
00:09:36,390 --> 00:09:42,480
And because of this relationship because the maximum value for log n plus one is m plus one, we can

194
00:09:42,480 --> 00:09:46,890
say ceiling of log n plus one is equal to m plus one.

195
00:09:46,890 --> 00:09:47,280
All right.

196
00:09:47,280 --> 00:09:48,960
And that is what we have over here.

197
00:09:48,960 --> 00:09:49,350
Right.

198
00:09:49,350 --> 00:09:52,710
Again that's what we need to prove this now because we know this.

199
00:09:52,710 --> 00:09:56,130
And we know M is equal to floor of log n.

200
00:09:56,130 --> 00:09:56,310
Right.

201
00:09:56,310 --> 00:09:58,350
So that's what m is equal to.

202
00:09:58,500 --> 00:09:59,160
All right.

203
00:09:59,160 --> 00:10:05,340
Therefore let me just substitute this over here I can say floor of log n plus one.

204
00:10:05,340 --> 00:10:06,600
So that's what is this over here.

205
00:10:06,600 --> 00:10:06,960
Right.

206
00:10:06,960 --> 00:10:07,470
Again.

207
00:10:07,470 --> 00:10:08,760
What is it that we're doing over here.

208
00:10:08,760 --> 00:10:10,290
We are substituting this.

209
00:10:10,320 --> 00:10:12,060
We are changing what we have over here.

210
00:10:12,060 --> 00:10:13,680
Ceiling of log n plus one.

211
00:10:13,680 --> 00:10:18,540
Now ceiling of log n plus one is M plus one which is floor of log n plus one.

212
00:10:18,540 --> 00:10:21,720
So I can say floor of log n plus one minus one.

213
00:10:21,720 --> 00:10:25,770
This minus one over here is what we have over here x is equal to h.

214
00:10:25,770 --> 00:10:30,690
Now these two cancel out and we are left with h is equal to floor of log n.

215
00:10:30,690 --> 00:10:32,070
So this is the proof.

216
00:10:32,070 --> 00:10:39,090
This is why the height of a balanced binary tree is equal to the floor of log n, where n is the number

217
00:10:39,090 --> 00:10:41,160
of nodes in the balanced binary tree.