1
00:00:00,720 --> 00:00:01,620
Hi everyone.

2
00:00:01,620 --> 00:00:04,350
So we have understood what trees are.

3
00:00:04,350 --> 00:00:06,960
Now let's try to understand binary trees.

4
00:00:06,990 --> 00:00:12,480
Now there are various types of trees, and the most common types of trees which you will encounter in

5
00:00:12,480 --> 00:00:14,370
coding interviews is about binary trees.

6
00:00:14,370 --> 00:00:17,340
So let's try to understand what these are in this video.

7
00:00:17,340 --> 00:00:22,980
Now a binary tree is a tree where each node can have at the most two children.

8
00:00:22,980 --> 00:00:29,430
Now, at the most two means every node can have zero, 1 or 2 children, but it cannot have three children.

9
00:00:29,430 --> 00:00:30,960
Now let's take an example.

10
00:00:30,960 --> 00:00:32,880
Let's say we have this tree over here.

11
00:00:32,880 --> 00:00:36,990
Now you can see that over here every node is having at the most two children.

12
00:00:36,990 --> 00:00:41,700
This node has two children, this node has zero children and this node has one child.

13
00:00:41,700 --> 00:00:43,620
So yes, this is a binary tree.

14
00:00:43,620 --> 00:00:48,840
But if you take a tree which looks like this, you can see that this node over here is having three

15
00:00:48,840 --> 00:00:49,380
children.

16
00:00:49,380 --> 00:00:52,260
And therefore this over here is not a binary tree.

17
00:00:52,260 --> 00:00:54,660
So we have understood what a binary tree is.

18
00:00:54,660 --> 00:00:57,240
Now let's take a look at these four concepts.

19
00:00:57,240 --> 00:01:00,030
We'll try to understand what is the height of a binary tree.

20
00:01:00,030 --> 00:01:01,500
What is the depth of a tree?

21
00:01:01,500 --> 00:01:03,930
What is the height balanced binary tree.

22
00:01:03,930 --> 00:01:10,560
And then finally we will try to understand why the height of a balanced binary tree is equal to log

23
00:01:10,560 --> 00:01:10,680
n.

24
00:01:10,680 --> 00:01:11,820
And then you have to floor it.

25
00:01:11,820 --> 00:01:12,150
All right.

26
00:01:12,180 --> 00:01:14,280
Now flooring means you're rounding it down.

27
00:01:14,280 --> 00:01:20,190
For example, if you find that log n is equal to 3.2, then when you floor this this becomes three.

28
00:01:20,190 --> 00:01:25,740
So the fourth point over here is that the height of a balanced binary tree will be equal to floor of

29
00:01:25,740 --> 00:01:26,220
log n.

30
00:01:26,220 --> 00:01:29,250
So in this video we will try to develop an intuition for this.

31
00:01:29,250 --> 00:01:33,990
And then in the next video we will try to look at a more rigorous mathematical proof for this.

32
00:01:33,990 --> 00:01:36,420
So let's go ahead and cover these four points.

33
00:01:36,420 --> 00:01:40,080
So first we start with the height and depth of a binary tree.

34
00:01:40,080 --> 00:01:46,020
And again over here you can note that when it comes to the depth of a node you can also call this level

35
00:01:46,020 --> 00:01:46,710
of a node.

36
00:01:46,710 --> 00:01:47,250
All right.

37
00:01:47,250 --> 00:01:49,470
So let's take an example to understand this.

38
00:01:49,470 --> 00:01:51,600
So over here we have a binary tree.

39
00:01:51,630 --> 00:01:55,110
Now first we are going to analyze the height and then the depth.

40
00:01:55,110 --> 00:01:55,470
All right.

41
00:01:55,470 --> 00:01:59,010
And when it comes to the height there are two things that we will take a look at.

42
00:01:59,010 --> 00:02:02,160
We will take a look at the height of a particular node.

43
00:02:02,160 --> 00:02:05,790
And then we will take a look at what is the height of the complete tree.

44
00:02:05,790 --> 00:02:12,180
Similarly for the depth, also, we will take a look at the depth of a node and the depth of the tree.

45
00:02:12,180 --> 00:02:14,940
So these are the four points that we will take a look at over here.

46
00:02:14,940 --> 00:02:16,350
Now let's get started.

47
00:02:16,350 --> 00:02:21,720
Now when you take a node and let's say you want to find out the height of that particular node, that

48
00:02:21,720 --> 00:02:27,990
is nothing but the number of edges on the longest path from that node to a leaf node.

49
00:02:27,990 --> 00:02:28,380
All right.

50
00:02:28,380 --> 00:02:30,960
So this is what you call the height of a node.

51
00:02:30,960 --> 00:02:35,010
And then the height of the tree is nothing but the height of the root node.

52
00:02:35,010 --> 00:02:39,060
Now let's try to understand this from this sample or example over here.

53
00:02:39,060 --> 00:02:41,850
Now for each node let's write the height.

54
00:02:42,210 --> 00:02:46,110
So if you take a look at that you can see that these are the heights of these nodes.

55
00:02:46,110 --> 00:02:49,680
So let's try to understand that over here this is a leaf node.

56
00:02:49,680 --> 00:02:54,930
And then if you want to go from this node to a leaf node you don't have any edge right.

57
00:02:54,930 --> 00:02:59,970
So over here the definition of height is the number of edges on the longest path from the node to a

58
00:02:59,970 --> 00:03:00,240
leaf.

59
00:03:00,240 --> 00:03:04,080
So that's why the height of a leaf node is equal to zero.

60
00:03:04,080 --> 00:03:09,330
Now if you take a look at this node over here, and if you want to go to the leaf node that's over here.

61
00:03:09,330 --> 00:03:09,510
Right.

62
00:03:09,510 --> 00:03:11,370
And then you can only go in this direction.

63
00:03:11,370 --> 00:03:14,280
You cannot go all the way back and then come to another leaf node.

64
00:03:14,280 --> 00:03:18,420
So that's why you from this node you have only one way because it has only one child.

65
00:03:18,420 --> 00:03:22,080
And then if you want to go to the leaf node there is one edge right.

66
00:03:22,080 --> 00:03:23,460
So there is one edge over here.

67
00:03:23,460 --> 00:03:26,550
So that's why the height of this node is equal to one.

68
00:03:26,550 --> 00:03:31,110
Similarly, if you take a look at the height of this node over here, you can see you have one.

69
00:03:31,110 --> 00:03:32,730
And then you have one more edge right.

70
00:03:32,730 --> 00:03:33,750
So you have two edges.

71
00:03:33,750 --> 00:03:36,990
So the height of this node over here is equal to two.

72
00:03:37,560 --> 00:03:39,780
And this again is a leaf node.

73
00:03:39,780 --> 00:03:41,820
So the height of this node is equal to zero.

74
00:03:41,820 --> 00:03:46,500
And when you take a look at this node over here now there are two ways in which you can go to a leaf

75
00:03:46,500 --> 00:03:46,800
node.

76
00:03:46,800 --> 00:03:52,380
You can either go in this direction and reach six, or you can go in this direction and reach two.

77
00:03:52,380 --> 00:03:57,990
But then the definition says that the height of a node is the longest path from the node to the leaf.

78
00:03:57,990 --> 00:04:01,260
So we take this direction and then we have one, two and three.

79
00:04:01,260 --> 00:04:02,340
So there are three edges.

80
00:04:02,340 --> 00:04:05,040
So that is why the height of this node is equal to three.

81
00:04:05,040 --> 00:04:05,670
All right.

82
00:04:05,670 --> 00:04:07,650
And similarly the height over here is zero.

83
00:04:07,650 --> 00:04:10,110
And over here is zero because these are leaf nodes.

84
00:04:10,110 --> 00:04:13,020
The height of this node over here is one because there is one edge.

85
00:04:13,020 --> 00:04:17,940
When you go want to go from this node to the leaf, the height of this node is equal to two because

86
00:04:17,940 --> 00:04:19,050
there are two edges.

87
00:04:19,050 --> 00:04:23,430
And when you take a look at this node over here again you have two ways to go to a leaf node.

88
00:04:23,430 --> 00:04:25,440
But then we take the longest path.

89
00:04:25,440 --> 00:04:28,740
So that is this path from 4 to 11 to 5 to 9.

90
00:04:28,740 --> 00:04:30,540
And you can see there are three edges.

91
00:04:30,540 --> 00:04:32,370
So the height of this node is three.

92
00:04:32,370 --> 00:04:35,250
And then the height of the root over here is four.

93
00:04:35,250 --> 00:04:39,600
Because if you want to take either path right, whether you take the left path or the right path if

94
00:04:39,600 --> 00:04:40,650
you take the longest path.

95
00:04:40,650 --> 00:04:42,780
So that's one possibility is this route.

96
00:04:42,780 --> 00:04:46,110
So you have four edges or you can take this route also.

97
00:04:46,590 --> 00:04:46,980
Right.

98
00:04:46,980 --> 00:04:48,480
Again you have four edges.

99
00:04:48,480 --> 00:04:51,330
So the height of this node over here is equal to four.

100
00:04:51,330 --> 00:04:54,900
So we have understood what the height of a particular node is.

101
00:04:54,900 --> 00:05:00,240
And then if we want the height of the tree of this complete tree it's nothing but the height of.

102
00:05:00,360 --> 00:05:02,190
The root note which is equal to four.

103
00:05:02,190 --> 00:05:05,070
So we can say that the height of this tree is equal to four.

104
00:05:05,100 --> 00:05:07,320
Now let's make a few observations over here.

105
00:05:07,320 --> 00:05:13,110
If we want to find the height of this node over here, notice that you just have to find the height

106
00:05:13,110 --> 00:05:17,850
of its children, which is two and zero, and take the maximum among the two, which is two.

107
00:05:17,850 --> 00:05:19,260
And then you have to add one.

108
00:05:19,260 --> 00:05:20,970
So two plus one gives you three.

109
00:05:20,970 --> 00:05:21,840
And why is that so?

110
00:05:21,840 --> 00:05:25,500
Because when you go from this node to this node there is one extra edge over here.

111
00:05:25,500 --> 00:05:25,770
Right.

112
00:05:25,770 --> 00:05:29,310
So that's why we have to do two plus one and we get three over here.

113
00:05:29,310 --> 00:05:29,820
All right.

114
00:05:29,850 --> 00:05:30,600
Now let's proceed.

115
00:05:30,600 --> 00:05:32,790
So we have understood what the height of a node is.

116
00:05:32,790 --> 00:05:37,260
And we have understood that the height of the tree is the height of the root node.

117
00:05:37,260 --> 00:05:37,710
All right.

118
00:05:37,710 --> 00:05:43,290
So remember when you are finding the height of a node you are always going down or to the leaf.

119
00:05:43,290 --> 00:05:45,300
Now what about the depth of a node.

120
00:05:45,300 --> 00:05:50,760
The depth of a node is nothing but the number of edges from the node to the root.

121
00:05:50,760 --> 00:05:53,250
So you are going to the root which is going upwards.

122
00:05:53,250 --> 00:05:53,610
All right.

123
00:05:53,610 --> 00:05:55,740
So that's the difference between height and depth.

124
00:05:55,740 --> 00:06:02,460
Now again if you want the depth of the tree then that's nothing but the height itself or the maximum

125
00:06:02,460 --> 00:06:05,430
depth of the tree is equal to the height of the tree.

126
00:06:05,430 --> 00:06:05,790
All right.

127
00:06:05,790 --> 00:06:08,820
So if you want the depth of the tree that's the maximum depth.

128
00:06:08,820 --> 00:06:10,950
And that will be equal to the height itself.

129
00:06:10,950 --> 00:06:14,040
Now let's go ahead and try to understand this from this example over here.

130
00:06:14,040 --> 00:06:15,570
So we have each node.

131
00:06:15,570 --> 00:06:18,720
Let's try to find the depth of every node first.

132
00:06:18,720 --> 00:06:19,020
All right.

133
00:06:19,020 --> 00:06:20,670
So let's write it over here.

134
00:06:21,270 --> 00:06:23,040
Now let's start at the root.

135
00:06:23,040 --> 00:06:27,060
Now again the definition says it's the number of edges from the node to the root.

136
00:06:27,060 --> 00:06:29,820
So when you're starting from the root you are already at the root.

137
00:06:29,820 --> 00:06:32,670
So there is no edge if you want to go to the root right.

138
00:06:32,670 --> 00:06:35,490
So that's why the depth of the root node is equal to zero.

139
00:06:35,490 --> 00:06:40,530
And then if you come to five and four if you want to go let's say let's take one example.

140
00:06:40,530 --> 00:06:44,550
If you want to go from five to the root node right you have to traverse one edge.

141
00:06:44,550 --> 00:06:45,780
So there is one edge over here.

142
00:06:45,780 --> 00:06:47,340
So that's the definition right.

143
00:06:47,370 --> 00:06:49,170
Number of edges from node to root.

144
00:06:49,170 --> 00:06:52,110
That's why the depth of this node over here is equal to one.

145
00:06:52,110 --> 00:06:55,200
Similarly the depth of this node also is equal to one.

146
00:06:55,200 --> 00:07:00,300
Now from this node which is three, if you want to go to the root you have to go two edges one and two.

147
00:07:00,330 --> 00:07:02,460
So that's why the depth over here is equal to two.

148
00:07:02,490 --> 00:07:07,620
Similarly for this node also the depth is equal to two because again you have to traverse two edges

149
00:07:07,620 --> 00:07:10,020
one and two right to go to the root node.

150
00:07:10,020 --> 00:07:12,990
Similarly for these two also the depth is equal to two.

151
00:07:12,990 --> 00:07:18,150
And then when you come over here if you want to go from this node to the root node, there are three

152
00:07:18,150 --> 00:07:19,890
edges one, two and three.

153
00:07:19,890 --> 00:07:20,130
Right.

154
00:07:20,130 --> 00:07:21,930
So that's why the depth over here is three.

155
00:07:21,930 --> 00:07:24,090
And over here also the depth is three.

156
00:07:24,090 --> 00:07:27,870
And then from this node to the root node you will have to traverse four edges.

157
00:07:27,870 --> 00:07:29,490
So the depth over here is four.

158
00:07:29,490 --> 00:07:31,860
And the depth over here is also four.

159
00:07:31,860 --> 00:07:36,330
Now you can understand from this why we call the depth of a node the level of a node.

160
00:07:36,330 --> 00:07:36,510
Right.

161
00:07:36,510 --> 00:07:37,710
Because take a look at this.

162
00:07:37,710 --> 00:07:39,150
Let's make an observation over here.

163
00:07:39,150 --> 00:07:43,200
You can see that over here these two nodes are at one level right.

164
00:07:43,200 --> 00:07:45,960
So they are the next level when you start from the root.

165
00:07:45,960 --> 00:07:49,710
So that's why instead of depth we can also say the level level of a node.

166
00:07:49,710 --> 00:07:51,270
So these two are level one.

167
00:07:51,270 --> 00:07:53,670
These four are at level two.

168
00:07:53,700 --> 00:07:56,010
Again these two nodes are at level three.

169
00:07:56,010 --> 00:07:59,070
And then these two nodes are at level four.

170
00:07:59,070 --> 00:07:59,610
All right.

171
00:07:59,610 --> 00:08:03,330
So we have understood what is the height and the depth of a node.

172
00:08:03,330 --> 00:08:08,250
And then we have also another point over here which says the maximum depth is equal to the height.

173
00:08:08,250 --> 00:08:08,520
Right.

174
00:08:08,520 --> 00:08:10,200
So that's the depth of this tree.

175
00:08:10,200 --> 00:08:14,670
So if you want to find out what is the depth of this tree, that would be the height which is equal

176
00:08:14,670 --> 00:08:15,210
to four.

177
00:08:15,210 --> 00:08:17,400
So you can see that this is the height.

178
00:08:17,400 --> 00:08:18,390
So that's four.

179
00:08:18,390 --> 00:08:19,560
Let me write that over here.

180
00:08:19,560 --> 00:08:21,300
And the maximum depth is over here.

181
00:08:21,300 --> 00:08:21,540
Right.

182
00:08:21,540 --> 00:08:24,150
So the maximum number of levels you have is four.

183
00:08:24,150 --> 00:08:25,980
So maximum depth is also four.

184
00:08:25,980 --> 00:08:29,640
So the maximum depth of a tree is equal to the height of the tree.

185
00:08:29,640 --> 00:08:30,240
All right.

186
00:08:30,240 --> 00:08:31,230
Let's proceed.

187
00:08:31,230 --> 00:08:34,590
Now there is another interesting point which you can note over here.

188
00:08:34,590 --> 00:08:39,000
Now when we create a tree we would first create these as nodes.

189
00:08:39,000 --> 00:08:40,740
And then it's left and right.

190
00:08:40,740 --> 00:08:42,780
Child initially would be set to null.

191
00:08:42,780 --> 00:08:43,170
All right.

192
00:08:43,170 --> 00:08:47,340
So when you take a look at these leaf nodes over here they don't have any children.

193
00:08:47,340 --> 00:08:47,610
Right.

194
00:08:47,610 --> 00:08:50,580
So they're left and right will be actually null.

195
00:08:50,580 --> 00:08:50,820
All right.

196
00:08:50,820 --> 00:08:52,230
So this over here will be null.

197
00:08:52,230 --> 00:08:53,550
And this over here will be null.

198
00:08:53,550 --> 00:08:57,630
Now the height of a null node is defined as minus one.

199
00:08:57,630 --> 00:08:59,610
And this is to make the math correct right.

200
00:08:59,640 --> 00:09:01,080
Now what's the math over here.

201
00:09:01,080 --> 00:09:03,030
Now let's write the nulls over here.

202
00:09:03,030 --> 00:09:05,610
So we have null wherever we don't have a child.

203
00:09:05,610 --> 00:09:06,000
All right.

204
00:09:06,000 --> 00:09:07,410
Now what's the math?

205
00:09:07,410 --> 00:09:12,600
Now the math is that we have seen that if you want to find the height of this node, for example, all

206
00:09:12,600 --> 00:09:16,710
you have to do is you have to take the maximum of the height of its children and add one to it.

207
00:09:16,710 --> 00:09:17,940
So over here you have two.

208
00:09:17,940 --> 00:09:18,990
And over here you have zero.

209
00:09:18,990 --> 00:09:21,570
So the maximum among two and zero is two.

210
00:09:21,570 --> 00:09:24,690
And then when you add one you get three which is the height of this node.

211
00:09:24,690 --> 00:09:26,700
So this is the math which is involved over here.

212
00:09:26,700 --> 00:09:32,460
Now for this math to hold true, we have defined that the height of a null node is equal to minus one.

213
00:09:32,460 --> 00:09:33,540
So how does that work.

214
00:09:33,540 --> 00:09:36,090
So over here this has a height of minus one.

215
00:09:36,090 --> 00:09:38,580
And this also has a height of minus one.

216
00:09:39,600 --> 00:09:45,060
So when you want to find the height of this node over here, its children, both of these have height

217
00:09:45,060 --> 00:09:45,810
minus one.

218
00:09:45,810 --> 00:09:48,780
So the maximum among these two is minus one itself.

219
00:09:48,780 --> 00:09:51,210
And then you add one to it and you get zero.

220
00:09:51,210 --> 00:09:52,980
So you can see that the math still holds.

221
00:09:52,980 --> 00:09:58,320
So for this purpose we have defined that the height of a null node is equal to minus one.

222
00:09:58,320 --> 00:09:58,830
All right.

223
00:09:58,860 --> 00:10:01,710
Now let's proceed and try to practice what we have learned.

224
00:10:01,710 --> 00:10:03,840
So over here I've drawn out a tree.

225
00:10:03,840 --> 00:10:04,140
All right.

226
00:10:04,140 --> 00:10:05,610
And the value does not matter.

227
00:10:05,610 --> 00:10:09,960
Now let's try to find the height and depth of every node of this tree over here.

228
00:10:09,960 --> 00:10:11,730
And we start with the height.

229
00:10:11,730 --> 00:10:15,120
And we know that the height of a null node is equal to minus one.

230
00:10:15,120 --> 00:10:16,530
So let me just write that over here.

231
00:10:16,530 --> 00:10:19,440
So we have null over here towards its left and right.

232
00:10:19,440 --> 00:10:21,900
And the height over here is minus one and minus one.

233
00:10:21,900 --> 00:10:27,120
So to find the height of this node all we have to do is we have to find the maximum height of its children

234
00:10:27,120 --> 00:10:28,410
which is minus one itself.

235
00:10:28,410 --> 00:10:29,760
And then we add one to it.

236
00:10:29,760 --> 00:10:31,890
So the height of this node is equal to zero.

237
00:10:31,890 --> 00:10:37,650
And similarly the height of this node over here is equal to one because its child's height is zero.

238
00:10:37,650 --> 00:10:39,090
And then we add one to it.

239
00:10:39,090 --> 00:10:41,040
So we get the height of this node as one.

240
00:10:41,040 --> 00:10:42,030
Now let's proceed.

241
00:10:42,030 --> 00:10:45,630
The height of this node over here will be one plus one which is equal to two.

242
00:10:46,260 --> 00:10:51,750
And if we take a look at these two nodes again they are leaf nodes which is the same case as what we

243
00:10:51,750 --> 00:10:52,350
have seen over here.

244
00:10:52,350 --> 00:10:54,540
So these have height is equal to zero.

245
00:10:55,150 --> 00:10:59,230
And then its parent over here will have zero plus one height, right?

246
00:10:59,230 --> 00:11:00,460
Which is equal to one itself.

247
00:11:00,460 --> 00:11:02,290
So the height over here is equal to one.

248
00:11:02,290 --> 00:11:06,820
And then if we want to find the height of this node we take the maximum among these two right which

249
00:11:06,820 --> 00:11:07,540
are its children.

250
00:11:07,540 --> 00:11:08,980
So the maximum is two.

251
00:11:09,010 --> 00:11:10,960
Then we add one to this two over here.

252
00:11:10,960 --> 00:11:13,240
So the height over here is equal to three.

253
00:11:13,420 --> 00:11:15,070
That's the height of each of these nodes.

254
00:11:15,070 --> 00:11:15,580
All right.

255
00:11:15,580 --> 00:11:18,610
And then let's take a look at the depth of every node.

256
00:11:18,610 --> 00:11:20,110
Now we start at the root.

257
00:11:20,110 --> 00:11:23,950
Remember the depth is the number of edges you have to traverse to get to the root.

258
00:11:23,980 --> 00:11:26,110
Now you're already at the root over here.

259
00:11:26,110 --> 00:11:28,480
So the depth over here is going to be equal to zero.

260
00:11:29,700 --> 00:11:34,260
Now, if you proceed to these two nodes, right, there is one edge that we have to traverse.

261
00:11:34,260 --> 00:11:37,230
So that's why the depth at this level is one.

262
00:11:37,230 --> 00:11:38,940
Or these are level one nodes.

263
00:11:38,940 --> 00:11:41,640
And over here again these three are level two nodes.

264
00:11:41,640 --> 00:11:43,200
Or the depth is equal to two.

265
00:11:43,230 --> 00:11:47,280
Because again you can see we have to traverse two edges to get to the root.

266
00:11:47,280 --> 00:11:50,370
And then over here the depth is going to be equal to three.

267
00:11:50,370 --> 00:11:56,850
Because to get from this node to the root node we have to traverse three edges right one two and three.

268
00:11:56,850 --> 00:11:57,390
All right.

269
00:11:57,390 --> 00:12:02,370
So again remember the depth of a node is also called the level of a node.

270
00:12:02,370 --> 00:12:05,820
Again we have seen why that is so because you can see this is one level.

271
00:12:05,820 --> 00:12:07,110
This is one level.

272
00:12:07,110 --> 00:12:08,730
And then this is one level.

273
00:12:08,730 --> 00:12:11,280
So over here every node has a depth one.

274
00:12:11,280 --> 00:12:12,930
Over here every node has a depth two.

275
00:12:12,930 --> 00:12:15,390
And over here every node has a depth three.

276
00:12:15,390 --> 00:12:20,250
And we have also discussed that the height of a tree is equal to the maximum depth.

277
00:12:20,250 --> 00:12:23,340
Now over here you can see that the maximum depth is equal to three.

278
00:12:23,340 --> 00:12:26,400
So the height of the tree is also equal to three.

279
00:12:26,400 --> 00:12:30,270
So we have seen that over here the height is three and the maximum depth is also three.

280
00:12:30,390 --> 00:12:30,750
All right.

281
00:12:30,750 --> 00:12:35,520
So we have discussed what the height of a node is, what the height of a tree is, what the depth of

282
00:12:35,520 --> 00:12:36,000
a node is.

283
00:12:36,000 --> 00:12:40,020
And that we have also discussed that maximum depth is equal to the height of the tree.

284
00:12:40,050 --> 00:12:44,520
Now let's proceed and try to understand what is a height balanced binary tree.

285
00:12:44,580 --> 00:12:47,520
Now first let's take a look at the definition of this.

286
00:12:47,520 --> 00:12:54,330
Now a height balanced binary tree is defined as a binary tree in which the depth of the two subtrees

287
00:12:54,330 --> 00:12:57,450
of every node never differs by more than one.

288
00:12:57,450 --> 00:13:00,480
Now again, let this definition be over here for a moment.

289
00:13:00,480 --> 00:13:04,950
First, let's try to understand what is the need for a height balanced binary tree.

290
00:13:04,950 --> 00:13:07,860
And then we will take a closer look at the definition over here.

291
00:13:07,860 --> 00:13:15,270
Now if a binary tree is skewed then computationally it's inefficient to perform operations.

292
00:13:15,270 --> 00:13:15,630
All right.

293
00:13:15,660 --> 00:13:17,910
Now what do I mean with a skewed binary tree.

294
00:13:17,910 --> 00:13:19,710
Now let's take an example.

295
00:13:19,710 --> 00:13:21,840
Let's say a binary tree looks like this.

296
00:13:21,840 --> 00:13:25,890
So you have this node which is pointing to this node which is pointing to this node.

297
00:13:25,890 --> 00:13:31,590
So technically this is a binary tree because you can say that every node is having at the most two children.

298
00:13:31,590 --> 00:13:31,860
Right.

299
00:13:31,860 --> 00:13:35,850
So this node has one child, this node has one child and this node has zero children.

300
00:13:35,850 --> 00:13:38,100
So this is actually a valid binary tree.

301
00:13:38,100 --> 00:13:40,740
But then you can see that it looks like a linked list.

302
00:13:40,740 --> 00:13:46,980
So all the benefits that we can derive from a binary tree type of data structure cannot be obtained

303
00:13:46,980 --> 00:13:47,430
over here.

304
00:13:47,430 --> 00:13:47,790
All right.

305
00:13:47,790 --> 00:13:51,120
So that's why we want to balance the binary tree.

306
00:13:51,120 --> 00:13:54,210
And that is the need for having a balanced binary.

307
00:13:54,210 --> 00:13:58,620
Now let's proceed and try to understand what a height balanced binary tree is.

308
00:13:58,650 --> 00:14:04,350
Over here again I have the definition a height balanced binary tree is a binary tree in which the depth

309
00:14:04,350 --> 00:14:08,790
of the two subtrees of every node never differs by more than one.

310
00:14:08,790 --> 00:14:14,010
Again, when we say that depth of a subtree, what we mean is actually the height, because this is

311
00:14:14,010 --> 00:14:18,090
actually maximum depth, and we know that maximum depth is nothing but height.

312
00:14:18,090 --> 00:14:24,330
So we can also say a binary tree in which the height of the two subtrees of every node never differs

313
00:14:24,330 --> 00:14:25,080
by more than one.

314
00:14:25,080 --> 00:14:26,220
So that's one and the same.

315
00:14:26,220 --> 00:14:32,070
Now let's take this example over here and understand why this tree over here is actually height balanced.

316
00:14:32,070 --> 00:14:38,400
So for this let's try to find out the difference between the height of the left child and the height

317
00:14:38,400 --> 00:14:40,260
of the right child for every node.

318
00:14:40,260 --> 00:14:45,630
And over here I have two lines to indicate that it's actually more so that that just means that, for

319
00:14:45,630 --> 00:14:50,490
example, if you find that the height of the left child is zero and then the height of the right child,

320
00:14:50,490 --> 00:14:53,910
let's say is equal to one, so zero minus one, we know it's minus one.

321
00:14:53,910 --> 00:14:56,640
But when we do mod of minus one that's equal to one.

322
00:14:56,640 --> 00:15:02,370
So we want to neglect the negative sign if it's applicable because we are only interested in the difference.

323
00:15:03,630 --> 00:15:06,750
Not whether the difference is minus one or plus one.

324
00:15:06,750 --> 00:15:07,110
All right.

325
00:15:07,110 --> 00:15:09,060
So that's why we have this mod over here.

326
00:15:09,060 --> 00:15:14,730
Now to start with let's write down the height of every node in this tree over here.

327
00:15:14,730 --> 00:15:18,060
Now we know that the height of leaf nodes are equal to zero.

328
00:15:18,060 --> 00:15:19,590
So we can write that over here.

329
00:15:19,590 --> 00:15:25,530
And when we proceed when we go up we just need to take the maximum height of its children and then add

330
00:15:25,530 --> 00:15:25,740
one.

331
00:15:25,740 --> 00:15:25,980
Right.

332
00:15:25,980 --> 00:15:28,290
So the height of this node over here will be one.

333
00:15:28,500 --> 00:15:33,360
And if you want to find the height of this node, that would be the maximum among zero and one which

334
00:15:33,360 --> 00:15:34,800
is one itself plus one.

335
00:15:34,800 --> 00:15:36,570
So the height over here is equal to two.

336
00:15:36,630 --> 00:15:38,970
And similarly the height over here is one.

337
00:15:38,970 --> 00:15:43,980
And then the height of the root node in this case is equal to three, which is the maximum among two

338
00:15:43,980 --> 00:15:45,180
and one plus one.

339
00:15:45,180 --> 00:15:47,220
So that's two plus one which is equal to three.

340
00:15:47,220 --> 00:15:49,500
Now let's proceed and write inside.

341
00:15:49,500 --> 00:15:54,270
Over here the difference between the height of the left child and the height of the right child.

342
00:15:54,270 --> 00:15:56,550
And again we're taking the absolute difference.

343
00:15:56,550 --> 00:16:00,960
Now over here its two children will have a height of minus one.

344
00:16:00,960 --> 00:16:01,230
Right.

345
00:16:01,230 --> 00:16:02,580
Because these are both null.

346
00:16:02,580 --> 00:16:06,180
And we have discussed that the height of a null node is equal to minus one.

347
00:16:06,180 --> 00:16:10,680
So in that case the difference between -1 and -1 is zero itself.

348
00:16:10,680 --> 00:16:13,080
So let me write the difference over here inside it.

349
00:16:13,080 --> 00:16:14,310
So that's zero.

350
00:16:14,310 --> 00:16:16,800
And that would be the case for every leaf node.

351
00:16:16,800 --> 00:16:16,950
Right.

352
00:16:16,950 --> 00:16:19,800
Because again over here also it's minus one and minus one.

353
00:16:19,800 --> 00:16:22,410
And that's the case over here and here as well.

354
00:16:22,410 --> 00:16:23,550
Now let's proceed.

355
00:16:23,550 --> 00:16:27,000
Now if we take a look at this node over here its two children.

356
00:16:27,000 --> 00:16:29,220
This child over here has a height of zero.

357
00:16:29,220 --> 00:16:31,170
And this child over here has a height of zero.

358
00:16:31,170 --> 00:16:31,440
Right.

359
00:16:31,440 --> 00:16:34,560
So when we subtract these two again we get zero.

360
00:16:34,560 --> 00:16:36,630
So let's write zero over here as well.

361
00:16:37,170 --> 00:16:39,510
Now let's take a look at this node over here.

362
00:16:39,510 --> 00:16:41,820
Its left child has a height of zero.

363
00:16:41,820 --> 00:16:44,490
And its right child has a height of one.

364
00:16:44,490 --> 00:16:46,890
So zero minus one gives us minus one.

365
00:16:46,890 --> 00:16:49,020
And then we are taking the absolute difference right.

366
00:16:49,020 --> 00:16:51,840
So that's why we can say that the difference is one.

367
00:16:53,090 --> 00:16:54,500
All right, now let's proceed.

368
00:16:54,500 --> 00:16:55,910
What about this node over here?

369
00:16:55,910 --> 00:16:58,220
Its left child has a height of minus one.

370
00:16:58,220 --> 00:16:59,720
Because over here its null.

371
00:16:59,720 --> 00:17:00,020
Right?

372
00:17:00,020 --> 00:17:01,790
And then the height over here is zero.

373
00:17:01,790 --> 00:17:04,130
Now the difference between -1 and 0.

374
00:17:04,130 --> 00:17:05,690
That's equal to one right.

375
00:17:05,690 --> 00:17:07,910
So let's write one over here.

376
00:17:09,880 --> 00:17:10,450
All right.

377
00:17:10,480 --> 00:17:12,460
Now let's take a look at this node over here.

378
00:17:12,460 --> 00:17:17,740
The height over here for its left child is two and the height for its right child is equal to one.

379
00:17:17,740 --> 00:17:20,170
Now the difference between 2 and 1 is one.

380
00:17:20,170 --> 00:17:21,490
So let's write that over here.

381
00:17:21,610 --> 00:17:24,790
Now you can see that for every node right.

382
00:17:24,790 --> 00:17:31,540
For every node if you consider its two subtrees then the difference of their heights does not differ

383
00:17:31,540 --> 00:17:32,500
by more than one.

384
00:17:32,500 --> 00:17:37,030
So that's why we can say that this is actually a height balanced binary tree.

385
00:17:37,030 --> 00:17:37,420
All right.

386
00:17:37,450 --> 00:17:40,810
Now let's also take an example which is not height balanced.

387
00:17:40,810 --> 00:17:43,540
Again we start by writing the heights of every node.

388
00:17:43,960 --> 00:17:45,160
Now these are leaf nodes.

389
00:17:45,160 --> 00:17:46,270
So they have height zero.

390
00:17:46,300 --> 00:17:48,280
This has height one which is zero plus one.

391
00:17:48,280 --> 00:17:50,680
This has height two which is one plus one.

392
00:17:50,680 --> 00:17:52,330
And then this has two plus one.

393
00:17:52,330 --> 00:17:54,550
So that's the height which is three over here.

394
00:17:54,550 --> 00:17:58,780
Now again let's find the difference between the height of the left child and the height of the right

395
00:17:58,780 --> 00:18:00,580
child for each of these nodes.

396
00:18:00,580 --> 00:18:06,040
For the case of the leaf nodes, we know that its children will have height minus one and minus one,

397
00:18:06,040 --> 00:18:06,220
right.

398
00:18:06,220 --> 00:18:07,150
Because these are null.

399
00:18:07,150 --> 00:18:08,530
So let's write zero.

400
00:18:08,560 --> 00:18:11,140
The difference between minus one and minus one is zero.

401
00:18:11,140 --> 00:18:12,490
So let's write that over here.

402
00:18:13,960 --> 00:18:14,320
All right.

403
00:18:14,320 --> 00:18:15,880
Now, what about this node over here?

404
00:18:15,880 --> 00:18:18,130
One child has a height of minus one.

405
00:18:18,130 --> 00:18:21,010
Because this over here is null and this has a height of zero.

406
00:18:21,010 --> 00:18:23,680
So the difference between 0 and -1 that's one.

407
00:18:23,680 --> 00:18:25,000
So let's write one over here.

408
00:18:25,600 --> 00:18:31,150
Now if you take a look at this node its left child has a height of zero and its right child has a height

409
00:18:31,150 --> 00:18:31,660
of one.

410
00:18:31,660 --> 00:18:34,000
So the difference between 0 and 1 that's one.

411
00:18:34,000 --> 00:18:35,350
So let's write one over here.

412
00:18:35,530 --> 00:18:37,600
And now let's consider this node.

413
00:18:37,600 --> 00:18:42,460
Its left child has a height of two and its right child has a height of zero.

414
00:18:42,460 --> 00:18:44,890
Now the difference between these two is equal to two.

415
00:18:44,890 --> 00:18:46,840
Right now this is not allowed.

416
00:18:46,840 --> 00:18:47,050
Right.

417
00:18:47,050 --> 00:18:51,280
Because over here we have discussed that the difference should not be greater than one.

418
00:18:51,280 --> 00:18:52,990
So this is violated over here.

419
00:18:52,990 --> 00:18:57,100
So that's why this example over here is not a height balanced tree.

420
00:18:57,250 --> 00:18:57,850
All right.

421
00:18:57,850 --> 00:19:00,460
So we have discussed what the height of a tree is.

422
00:19:00,460 --> 00:19:03,040
What the height of a node is, what the depth of a node is.

423
00:19:03,040 --> 00:19:06,790
And we have also discussed what a height balanced binary tree is.

424
00:19:06,790 --> 00:19:12,190
Now let's move ahead to the last point in this video, which is to try to understand the height of a

425
00:19:12,190 --> 00:19:12,910
binary tree.

426
00:19:12,940 --> 00:19:20,380
Now, if a binary tree has n nodes, then the height of this binary tree over here will be in between

427
00:19:20,380 --> 00:19:22,540
log n and n minus one.

428
00:19:22,540 --> 00:19:25,900
And when we say log n this is actually for log n.

429
00:19:25,900 --> 00:19:26,440
All right.

430
00:19:27,400 --> 00:19:27,760
Now.

431
00:19:27,760 --> 00:19:28,690
What do I mean with this?

432
00:19:28,690 --> 00:19:30,970
Let me just quickly explain that over here.

433
00:19:30,970 --> 00:19:33,520
Let's say you have five nodes.

434
00:19:33,520 --> 00:19:33,910
All right.

435
00:19:33,910 --> 00:19:36,580
Now log five will be two point something.

436
00:19:36,580 --> 00:19:38,890
We know log four is equal to two.

437
00:19:39,650 --> 00:19:42,650
And log eight is equal to three.

438
00:19:42,650 --> 00:19:45,410
Now everything in between will be two point something.

439
00:19:45,410 --> 00:19:45,620
Right.

440
00:19:45,620 --> 00:19:47,990
So log five will be two point something.

441
00:19:47,990 --> 00:19:50,840
Now we know that the height of a tree cannot be a decimal right.

442
00:19:50,840 --> 00:19:52,430
So we have to floor this.

443
00:19:52,430 --> 00:19:59,030
So when we floor this this will be equal to two itself because this is 2.1 or 2.2 something two point

444
00:19:59,030 --> 00:19:59,510
something.

445
00:19:59,510 --> 00:20:01,640
And flooring it means we are rounding it down.

446
00:20:01,640 --> 00:20:03,170
And that gives us two itself.

447
00:20:03,170 --> 00:20:03,680
All right.

448
00:20:03,680 --> 00:20:10,250
So what is mentioned over here is that the height of a binary tree will be in between floor of log n

449
00:20:10,250 --> 00:20:11,660
and n minus one.

450
00:20:11,660 --> 00:20:14,960
Now let's first develop an intuition for this.

451
00:20:14,960 --> 00:20:18,680
And in the next video we will discuss the mathematical proof for this.

452
00:20:18,680 --> 00:20:22,310
Now when will a binary tree have minimum height?

453
00:20:22,310 --> 00:20:25,400
It would be the case when the tree is balanced, right?

454
00:20:25,400 --> 00:20:26,960
So let's try to understand that.

455
00:20:26,960 --> 00:20:29,360
For example this is a balanced binary tree.

456
00:20:29,360 --> 00:20:35,300
Now you can see that if you take any node, its left and right subtrees will not have a difference of

457
00:20:35,300 --> 00:20:37,970
more than one when you take their respective heights.

458
00:20:37,970 --> 00:20:38,330
All right.

459
00:20:38,330 --> 00:20:44,150
So this is actually the tree that you can construct with five nodes with the minimum height.

460
00:20:44,180 --> 00:20:46,820
Now again over here we are developing an intuition.

461
00:20:46,820 --> 00:20:47,540
Now why is that.

462
00:20:47,540 --> 00:20:51,830
So let's also take a look at the tree that we can construct which has the maximum height.

463
00:20:52,280 --> 00:20:55,580
Now if you want to do that it would look something like this right.

464
00:20:56,990 --> 00:21:01,220
So you can see that the height of this tree over here is one, two, three, four.

465
00:21:01,220 --> 00:21:01,520
Right.

466
00:21:01,520 --> 00:21:03,050
So the height over here is four.

467
00:21:03,050 --> 00:21:08,900
But if you take a look at this tree over here, the height is equal to floor of log five which is equal

468
00:21:08,900 --> 00:21:09,350
to two.

469
00:21:09,350 --> 00:21:11,420
And again you can see it over here it's two right.

470
00:21:11,420 --> 00:21:13,730
So this over here has a height zero.

471
00:21:13,730 --> 00:21:15,290
This node has a height one.

472
00:21:15,290 --> 00:21:16,970
And this node has a height two.

473
00:21:16,970 --> 00:21:20,210
And we know that the height of the tree is nothing but the height of the root node.

474
00:21:20,210 --> 00:21:22,730
And over here the height of the root node is equal to two.

475
00:21:22,730 --> 00:21:25,220
So this tree has height two.

476
00:21:25,220 --> 00:21:30,140
And when you take a look at this binary tree you can see that the height is equal to four.

477
00:21:30,140 --> 00:21:30,650
Right.

478
00:21:30,800 --> 00:21:32,330
So the height over here is four.

479
00:21:32,330 --> 00:21:34,370
And again we have five nodes.

480
00:21:35,490 --> 00:21:40,830
So four is actually five minus one, which is n minus one, which is what we have over here.

481
00:21:40,830 --> 00:21:41,070
Right.

482
00:21:41,070 --> 00:21:42,450
So five over here is n.

483
00:21:42,450 --> 00:21:44,040
So this is actually n minus one.

484
00:21:44,040 --> 00:21:45,960
So this is actually an intuition right.

485
00:21:45,960 --> 00:21:47,730
You can see if you just have it like this.

486
00:21:47,730 --> 00:21:50,700
So this binary tree over here looks just like a linked list.

487
00:21:50,730 --> 00:21:53,310
Now over here because everything is going in one direction.

488
00:21:53,310 --> 00:21:54,480
The height is great right.

489
00:21:54,480 --> 00:21:57,300
The height is the maximum possible which is equal to four.

490
00:21:57,300 --> 00:22:01,530
But then this one over here is compact because it's it's balanced.

491
00:22:01,530 --> 00:22:01,950
Right.

492
00:22:01,950 --> 00:22:04,740
And you can see that the height over here is just two.

493
00:22:04,740 --> 00:22:08,400
And again that's floor of log n n over here is equal to five.

494
00:22:08,400 --> 00:22:09,000
All right.

495
00:22:09,030 --> 00:22:10,500
Now let's proceed.

496
00:22:10,500 --> 00:22:13,290
And let's again continue developing our intuition.

497
00:22:13,290 --> 00:22:16,020
So over here we have our balanced binary tree.

498
00:22:16,020 --> 00:22:20,430
Now let's explore the relationship between the number of nodes and the height.

499
00:22:20,460 --> 00:22:24,390
Now we have already discussed that the height is equal to log n.

500
00:22:24,390 --> 00:22:25,890
And then you have to just floor it.

501
00:22:27,870 --> 00:22:28,230
All right.

502
00:22:28,230 --> 00:22:31,680
Now let's try to take a look at this and see how this works out.

503
00:22:31,710 --> 00:22:33,540
Now over here when n is equal to five.

504
00:22:33,540 --> 00:22:38,370
So 12345 we have seen that the height is equal to two and we get two.

505
00:22:38,370 --> 00:22:42,570
When we do floor of log five, log five again will be two point something.

506
00:22:42,570 --> 00:22:44,730
And when we floor it we are rounding down.

507
00:22:44,730 --> 00:22:45,930
And that gives us two.

508
00:22:45,930 --> 00:22:47,940
Now let's say we add one more node.

509
00:22:47,940 --> 00:22:49,650
So let's say we added over here.

510
00:22:49,650 --> 00:22:51,180
Now we have six nodes.

511
00:22:51,180 --> 00:22:55,890
And if we do log six and again I'm not writing floor but we have to do floor.

512
00:22:55,890 --> 00:22:56,250
All right.

513
00:22:56,250 --> 00:22:58,560
So log six will be two point something.

514
00:22:58,560 --> 00:23:00,780
Now the height of a tree cannot be decimal value.

515
00:23:00,780 --> 00:23:03,210
So when we floor this again we get two.

516
00:23:03,210 --> 00:23:04,830
Now let's add one more node.

517
00:23:04,830 --> 00:23:06,270
So we have seven nodes.

518
00:23:06,270 --> 00:23:07,380
Again log seven.

519
00:23:07,380 --> 00:23:09,060
When we floor it we will get two.

520
00:23:09,060 --> 00:23:11,970
Now if we add one more node we have eight nodes.

521
00:23:11,970 --> 00:23:14,790
And when we do log eight that's equal to three right.

522
00:23:14,790 --> 00:23:17,910
So we have already discussed why log eight is equal to three.

523
00:23:17,910 --> 00:23:18,570
Log eight.

524
00:23:18,570 --> 00:23:19,740
In other terms right.

525
00:23:19,740 --> 00:23:25,890
In other terms if you want to find out log eight, this is nothing but asking two to what power is equal

526
00:23:25,890 --> 00:23:26,400
to eight.

527
00:23:26,400 --> 00:23:28,650
And the answer for this is equal to three.

528
00:23:28,650 --> 00:23:30,480
So that's why log eight is equal to three.

529
00:23:30,480 --> 00:23:35,310
And remember whenever we discuss log over here the base is equal to two because this is a binary tree.

530
00:23:35,370 --> 00:23:36,750
Now let's proceed.

531
00:23:37,320 --> 00:23:44,370
Now if we had inserted the eight nodes into the binary tree in this manner, then you can see that the

532
00:23:44,370 --> 00:23:45,690
height is not equal to three.

533
00:23:45,690 --> 00:23:51,270
For example, over here the height when you go from this node to this node you have one, two, three

534
00:23:51,270 --> 00:23:51,810
and four.

535
00:23:51,810 --> 00:23:55,500
So the height of the root node is equal to four which is not equal to three.

536
00:23:55,500 --> 00:23:56,880
And we have only eight nodes.

537
00:23:56,880 --> 00:24:00,510
But then the thing is that this tree over here is not balanced.

538
00:24:00,510 --> 00:24:04,950
So the height of a balanced binary tree will be log n.

539
00:24:04,950 --> 00:24:06,600
And then we have to just floor it.