1
00:00:00,580 --> 00:00:01,510
Hi everyone!

2
00:00:01,510 --> 00:00:04,840
In this video let's learn more about Binary trees.

3
00:00:04,870 --> 00:00:10,030
Now understanding these concepts will prepare us to solve a variety of questions.

4
00:00:10,030 --> 00:00:11,410
So let's get started.

5
00:00:11,410 --> 00:00:14,230
These are the six topics which we will explore.

6
00:00:14,230 --> 00:00:17,890
First, we are going to learn what we mean with perfect binary trees.

7
00:00:17,890 --> 00:00:24,190
Now a perfect binary tree is a tree which has all its levels completely filled.

8
00:00:24,190 --> 00:00:26,200
Now let's take an example.

9
00:00:26,200 --> 00:00:28,210
So over here we have a binary tree.

10
00:00:28,210 --> 00:00:30,460
And you can see this is level zero.

11
00:00:30,460 --> 00:00:31,900
And this is level one.

12
00:00:31,900 --> 00:00:33,580
And it's completely filled.

13
00:00:33,580 --> 00:00:34,000
All right.

14
00:00:34,030 --> 00:00:37,270
Now if the next level is filled it would look like this.

15
00:00:37,270 --> 00:00:40,420
So again this also is a perfect binary tree.

16
00:00:40,420 --> 00:00:47,680
Now if I have one more node in the next level, then you can see that this level over here is not completely

17
00:00:47,680 --> 00:00:48,130
filled.

18
00:00:48,130 --> 00:00:52,240
And therefore this over here is not a perfect binary tree.

19
00:00:52,270 --> 00:00:52,690
All right.

20
00:00:52,690 --> 00:00:58,630
So if this node was not there then we can say this part is actually a perfect binary tree.

21
00:00:58,630 --> 00:00:59,170
All right.

22
00:00:59,200 --> 00:01:00,160
Now what else.

23
00:01:00,160 --> 00:01:02,530
What else can we observe about a perfect binary tree.

24
00:01:02,530 --> 00:01:09,370
You can see that the number of nodes in the last level, which is this level over here is equal to one

25
00:01:09,370 --> 00:01:13,480
plus the nodes which are there in all previous levels.

26
00:01:13,660 --> 00:01:15,430
For example, over here we have four.

27
00:01:15,430 --> 00:01:18,010
And in previous levels you can see we have three right.

28
00:01:18,010 --> 00:01:18,850
So this is three.

29
00:01:18,850 --> 00:01:20,890
And in the last level we have four nodes.

30
00:01:20,890 --> 00:01:23,440
And four is equal to three plus one.

31
00:01:23,440 --> 00:01:28,150
Again if the next level was filled let's take a look at how that would look.

32
00:01:28,150 --> 00:01:30,100
So let me just draw that over here.

33
00:01:30,100 --> 00:01:35,140
So if we fill this up you can see that in this level we have eight nodes.

34
00:01:35,140 --> 00:01:36,250
So this is eight right.

35
00:01:36,250 --> 00:01:37,030
So eight.

36
00:01:37,030 --> 00:01:41,650
And in all the previous nodes together we have four plus two plus one which is seven.

37
00:01:41,650 --> 00:01:43,870
So you can see eight is equal to seven plus one.

38
00:01:43,870 --> 00:01:49,240
So the number of nodes in the last level is equal to one plus all the previous nodes.

39
00:01:49,240 --> 00:01:52,570
So this is also something interesting about a perfect binary tree.

40
00:01:52,570 --> 00:01:58,930
And then you can see that the number of nodes in the last level is two times the number of nodes in

41
00:01:58,930 --> 00:01:59,920
the previous level.

42
00:01:59,920 --> 00:02:02,140
For example, over here let's take a look.

43
00:02:02,140 --> 00:02:03,520
We have eight nodes over here.

44
00:02:03,520 --> 00:02:06,250
And in the previous level we have four nodes.

45
00:02:06,250 --> 00:02:09,700
And this eight over here is equal to four into two.

46
00:02:09,730 --> 00:02:11,170
So that's what we have over here.

47
00:02:11,170 --> 00:02:15,160
So these are some interesting observations about a perfect binary tree.

48
00:02:15,700 --> 00:02:20,800
Let's now proceed to point number two which is an almost complete binary tree.

49
00:02:20,800 --> 00:02:24,670
Now this is a tree which should not be a perfect binary tree.

50
00:02:24,670 --> 00:02:30,070
And then it's just that we have to fill the nodes level by level to it from left to right.

51
00:02:30,100 --> 00:02:31,390
Now let's take an example.

52
00:02:31,390 --> 00:02:34,120
Let's say we have one node over here and one node over here.

53
00:02:34,120 --> 00:02:36,940
This over here is an almost complete binary tree.

54
00:02:36,940 --> 00:02:41,320
Now if we have one more node over here, you can see that this is actually a perfect binary tree.

55
00:02:41,320 --> 00:02:44,050
So this is not an almost complete binary tree.

56
00:02:44,050 --> 00:02:48,940
But then if you have one more node you can see, yes, this is an almost complete binary tree.

57
00:02:48,940 --> 00:02:53,560
And then when we fill the next node, we just have to make sure that we fill from left to right.

58
00:02:53,560 --> 00:02:54,850
So we cannot add it over here.

59
00:02:54,850 --> 00:02:58,870
So if you do that over here then this is not an almost complete binary tree.

60
00:02:58,870 --> 00:02:59,290
All right.

61
00:02:59,290 --> 00:03:01,060
So instead of that we should add over here.

62
00:03:01,060 --> 00:03:03,400
So this is still an almost complete binary tree.

63
00:03:03,400 --> 00:03:05,230
And the next node should be added over here.

64
00:03:05,230 --> 00:03:09,850
And if we add one more node it will become a perfect binary tree if it's added over here.

65
00:03:09,850 --> 00:03:13,330
So this type of a tree is called an almost complete binary tree.

66
00:03:13,330 --> 00:03:18,010
So we have seen what a perfect binary tree is and an almost complete binary tree.

67
00:03:18,040 --> 00:03:22,270
Now these two together is what we call a complete binary tree.

68
00:03:22,270 --> 00:03:22,840
All right.

69
00:03:22,870 --> 00:03:28,810
Now what is that that we can conclude this is a tree which has all the nodes completely filled, all

70
00:03:28,810 --> 00:03:32,380
the positions completely filled till the second last level.

71
00:03:32,380 --> 00:03:36,640
And in the last level, the nodes are filled from left to right.

72
00:03:37,190 --> 00:03:43,760
And also it can have all the levels completely filled because a perfect binary tree is also a complete

73
00:03:43,760 --> 00:03:44,660
binary tree.

74
00:03:44,660 --> 00:03:49,430
All right, so we have understood what a perfect binary tree is, what an almost complete binary tree

75
00:03:49,430 --> 00:03:51,980
is, and what a complete binary tree is.

76
00:03:51,980 --> 00:03:52,490
All right.

77
00:03:52,520 --> 00:03:53,600
Now let's proceed.

78
00:03:53,600 --> 00:03:56,990
Let's now take a look at the next point, which is a full tree.

79
00:03:56,990 --> 00:03:59,120
Again, these are just important terminology.

80
00:03:59,120 --> 00:04:06,290
Now a full tree is a tree for which each node has zero children or exactly two children.

81
00:04:06,290 --> 00:04:07,880
Let's take a few examples.

82
00:04:07,880 --> 00:04:11,960
Over here you can see that every node has 0 or 2 children, right?

83
00:04:11,960 --> 00:04:16,280
This node has two children, this node has zero children and this node has zero children.

84
00:04:16,280 --> 00:04:17,690
That's the same case over here.

85
00:04:17,690 --> 00:04:19,010
This one has two children.

86
00:04:19,010 --> 00:04:20,030
This has two children.

87
00:04:20,030 --> 00:04:22,280
And these nodes have zero children.

88
00:04:22,280 --> 00:04:24,230
So this also is a full tree.

89
00:04:24,230 --> 00:04:29,480
And this also over here you have two children two children, zero children, zero children and zero

90
00:04:29,480 --> 00:04:29,810
children.

91
00:04:29,810 --> 00:04:32,510
So this tree over here is also a full tree.

92
00:04:32,510 --> 00:04:37,370
But then if you have this tree you can see this node has one child, right?

93
00:04:37,370 --> 00:04:40,280
Therefore, this tree is not a full tree.

94
00:04:40,280 --> 00:04:40,820
All right.

95
00:04:40,850 --> 00:04:42,500
Now let's go ahead and continue.

96
00:04:42,500 --> 00:04:46,070
Let's take a complete binary tree which is zero indexed.

97
00:04:46,070 --> 00:04:52,010
And using this tree, let's try to find the range of leaves and the range of internal nodes.

98
00:04:52,010 --> 00:04:57,380
Now let's take two examples and let's just mark the indices over here we are taking that this tree is

99
00:04:57,380 --> 00:05:00,050
zero index which means this is index zero.

100
00:05:00,050 --> 00:05:01,700
This is one this is two etc..

101
00:05:01,700 --> 00:05:02,090
All right.

102
00:05:02,090 --> 00:05:03,650
So let's write the indices over here.

103
00:05:03,680 --> 00:05:06,620
Now over here you can see there are seven nodes.

104
00:05:06,620 --> 00:05:09,260
That's why the indices range from 0 to 6.

105
00:05:09,260 --> 00:05:12,470
And what about this tree over here you can see there are five nodes.

106
00:05:12,470 --> 00:05:15,050
And the indices range from 0 to 4.

107
00:05:15,080 --> 00:05:15,530
All right.

108
00:05:15,560 --> 00:05:17,780
Now if you want to know the range of leaves.

109
00:05:17,780 --> 00:05:20,810
And again remember leaves are just nodes without children.

110
00:05:20,810 --> 00:05:23,330
So you can see over here these are the leaves.

111
00:05:23,330 --> 00:05:25,610
And in this case these two are leaves.

112
00:05:25,610 --> 00:05:27,140
And this one over here is a leaf.

113
00:05:27,140 --> 00:05:29,660
Now in a complete binary tree.

114
00:05:29,660 --> 00:05:34,940
If you want to know the range of leaves then all you have to do is you have to take flow of n by two

115
00:05:34,940 --> 00:05:36,530
and you have to find n minus one.

116
00:05:36,530 --> 00:05:38,420
So these will be the extreme indices.

117
00:05:38,420 --> 00:05:40,970
So let's try it out in these two cases.

118
00:05:40,970 --> 00:05:46,550
And again why are we studying this later when we study a concept called heaps binary heaps.

119
00:05:46,730 --> 00:05:49,760
Actually these are complete binary trees.

120
00:05:49,760 --> 00:05:50,120
All right.

121
00:05:50,120 --> 00:05:51,440
So we will see this later.

122
00:05:51,440 --> 00:05:54,740
Again we will discuss this once more when we encounter this.

123
00:05:54,740 --> 00:05:56,750
But let's just introduce the topic over here.

124
00:05:56,750 --> 00:06:02,390
Now in a complete binary tree we have seen that the range of leaves or the indices of the leaves will

125
00:06:02,390 --> 00:06:05,330
be from flow of n by two to n minus one.

126
00:06:05,330 --> 00:06:10,250
And again, this is the case where the complete binary tree is zero indexed.

127
00:06:10,250 --> 00:06:10,730
All right.

128
00:06:10,760 --> 00:06:14,990
Now what will be flow of n by two seven by two gives us 3.5.

129
00:06:14,990 --> 00:06:17,030
And when we flow it we get three.

130
00:06:17,030 --> 00:06:17,450
All right.

131
00:06:17,450 --> 00:06:21,650
And n minus one which is seven minus one is equal to six.

132
00:06:21,650 --> 00:06:25,910
So you can see that the range of the leaves are from 3 to 6 which is correct.

133
00:06:25,910 --> 00:06:26,090
Right.

134
00:06:26,090 --> 00:06:28,160
We have three four, five and six.

135
00:06:28,160 --> 00:06:29,030
So that's working.

136
00:06:29,030 --> 00:06:30,500
Now what about this case.

137
00:06:30,500 --> 00:06:31,940
Let n is equal to five.

138
00:06:31,940 --> 00:06:33,860
So five by two is 2.5.

139
00:06:33,860 --> 00:06:35,990
And when we flow it we get two.

140
00:06:35,990 --> 00:06:38,810
And n minus one is five minus one which is four.

141
00:06:38,810 --> 00:06:42,230
And the leaves over here are two three and four.

142
00:06:42,230 --> 00:06:43,580
So you can see it's working right.

143
00:06:43,580 --> 00:06:48,290
So 2 to 4 has two three and four and 3 to 6 has 345 and six.

144
00:06:48,290 --> 00:06:52,400
Now the other nodes will be internal nodes right.

145
00:06:52,400 --> 00:06:55,820
So all the nodes other than the leaf nodes are internal nodes.

146
00:06:55,820 --> 00:06:57,710
So we have already covered these.

147
00:06:57,710 --> 00:07:02,750
And again when there are n nodes and they are zero indexed, all the indices will be starting from zero

148
00:07:02,750 --> 00:07:04,640
and it will go on till n minus one.

149
00:07:04,640 --> 00:07:05,930
So we have covered these.

150
00:07:05,930 --> 00:07:07,550
So the remaining will be internal nodes.

151
00:07:07,550 --> 00:07:11,120
So that would be zero to flow of n by two minus one.

152
00:07:11,120 --> 00:07:12,170
And that's working over here.

153
00:07:12,170 --> 00:07:12,440
Right.

154
00:07:12,440 --> 00:07:14,600
We have seen flow of seven by two is three.

155
00:07:14,600 --> 00:07:16,880
So if we subtract one from it we will get two.

156
00:07:16,880 --> 00:07:18,650
And you can see that zero one and two.

157
00:07:18,680 --> 00:07:20,360
These are the internal nodes over here.

158
00:07:20,360 --> 00:07:24,830
And similarly in this case you can see zero and one are the internal nodes.

159
00:07:24,830 --> 00:07:28,160
Flow of five by two was two two minus one gives us one.

160
00:07:28,160 --> 00:07:29,780
And that's what we have over here one.

161
00:07:29,780 --> 00:07:33,140
So 0 to 1 so zero and one are the internal nodes.

162
00:07:33,140 --> 00:07:33,650
All right.

163
00:07:33,650 --> 00:07:35,540
So we have covered these topics.

164
00:07:35,540 --> 00:07:37,430
We have seen what a perfect binary tree is.

165
00:07:37,430 --> 00:07:40,790
What an almost complete binary tree is, what a complete binary tree is.

166
00:07:40,790 --> 00:07:42,680
And we have also seen what a full tree is.

167
00:07:42,680 --> 00:07:43,040
All right.

168
00:07:43,040 --> 00:07:46,400
And we have discussed the range of leaves and range of internal nodes.

169
00:07:46,400 --> 00:07:51,350
Now let's just introduce one more topic before we end this video, which is tree traversal.

170
00:07:51,350 --> 00:07:54,110
Now what do we mean with traversing a tree?

171
00:07:54,110 --> 00:07:57,440
Traversing a tree means just visiting every node one time.

172
00:07:57,440 --> 00:07:57,830
All right.

173
00:07:57,830 --> 00:07:59,930
So for example over here we have this tree.

174
00:07:59,960 --> 00:08:01,820
Now if we want to visit every node.

175
00:08:01,820 --> 00:08:04,820
So we want to go to 35746 11.

176
00:08:04,820 --> 00:08:07,640
So we would want to do that for multiple reasons.

177
00:08:07,640 --> 00:08:14,180
And again in algorithm questions also you may need to traverse the tree for different types of questions.

178
00:08:14,180 --> 00:08:16,730
Now we can do that in different ways.

179
00:08:16,730 --> 00:08:17,090
All right.

180
00:08:17,090 --> 00:08:22,760
So we will see this in detail when we discuss questions where we will see how we can implement breadth

181
00:08:22,760 --> 00:08:25,670
first and depth first traversal in binary trees.

182
00:08:25,670 --> 00:08:27,440
So we will see that in a future video.

183
00:08:27,440 --> 00:08:29,720
But over here we are just introducing the concept.

184
00:08:29,720 --> 00:08:32,720
So traversing a tree means visiting every node one time.

185
00:08:32,720 --> 00:08:34,250
We can do it in different ways.

186
00:08:34,250 --> 00:08:36,800
Now over here as an introduction let's discuss.

187
00:08:37,100 --> 00:08:41,030
What do we mean with breadth first traversal or breadth first search?

188
00:08:41,060 --> 00:08:44,120
It's also called BFS or breadth first traversal.

189
00:08:44,150 --> 00:08:50,000
Now in this case, if you traverse or visit the nodes in the tree in this manner, we would visit three,

190
00:08:50,000 --> 00:08:53,120
then five and seven, and then four and four, six and 11.

191
00:08:53,120 --> 00:08:55,130
So three, five, seven, four, six, 11.

192
00:08:55,130 --> 00:08:57,500
So you can see that we are visiting level by level.

193
00:08:57,500 --> 00:09:03,680
So we are visiting the node three, then five and seven which are in the same level, then four six

194
00:09:03,680 --> 00:09:06,110
and level 11 which are in the same level.

195
00:09:06,110 --> 00:09:08,570
So this is what we call breadth first traversal.

196
00:09:08,570 --> 00:09:10,820
And then we have depth first traversal.

197
00:09:10,850 --> 00:09:14,420
Now there are different ways of doing a depth first traversal.

198
00:09:14,420 --> 00:09:16,130
So let's not discuss that over here.

199
00:09:16,130 --> 00:09:17,720
We will have a future video for that.

200
00:09:17,720 --> 00:09:20,270
But over here let's just develop the intuition.

201
00:09:20,270 --> 00:09:24,020
So in the case of breadth first we have seen that we are going wide first.

202
00:09:24,020 --> 00:09:24,290
Right.

203
00:09:24,290 --> 00:09:25,790
So we are going in this direction.

204
00:09:25,790 --> 00:09:29,900
Now in the case of depth first traversal we would be going deep first.

205
00:09:29,900 --> 00:09:33,350
So that means for example we could go from here to here to here.

206
00:09:33,350 --> 00:09:35,600
So we are going deep before we are going broad.

207
00:09:35,600 --> 00:09:38,780
And after going to four probably we go to five.

208
00:09:38,780 --> 00:09:39,740
Then we go to six.

209
00:09:39,740 --> 00:09:40,970
Then we come to three.

210
00:09:40,970 --> 00:09:43,280
Then we go to seven and then to 11.

211
00:09:43,280 --> 00:09:46,340
So that's again one way of doing a DFS.

212
00:09:46,340 --> 00:09:47,990
But it can be done in multiple ways.

213
00:09:47,990 --> 00:09:54,200
But the intuition that we try to develop over here is that in the case of depth first traversal or DFS

214
00:09:54,200 --> 00:09:56,600
depth first search, we are going deep first.

215
00:09:56,600 --> 00:10:00,140
But in the case of breadth first traversal we are going broad first.

216
00:10:00,140 --> 00:10:00,680
All right.

217
00:10:00,680 --> 00:10:04,850
And again traversal means visiting every node of the tree one time.