1
00:00:01,000 --> 00:00:01,640
Hi, everyone.

2
00:00:01,660 --> 00:00:08,470
So in this video, we are going to solve this question, find the maximum depth of a binary tree, OK,

3
00:00:08,860 --> 00:00:13,450
find the maximum depth of a binary tree that either way to solve this equation, the better way to say

4
00:00:13,450 --> 00:00:17,020
this question is basically find the height of a binary tree.

5
00:00:17,050 --> 00:00:17,410
OK.

6
00:00:18,470 --> 00:00:21,110
We have to find the height of a binary tree.

7
00:00:21,260 --> 00:00:23,640
OK, so let us consider some example.

8
00:00:23,660 --> 00:00:27,170
So if this is the military now, what is the height?

9
00:00:27,740 --> 00:00:29,330
So basically, this is the root node.

10
00:00:31,270 --> 00:00:38,260
OK, so this is level one, this is level two, and this is level three, OK, since they are a maximum

11
00:00:38,260 --> 00:00:38,890
three levels.

12
00:00:39,010 --> 00:00:44,830
So the height of this binded is basically three height or you can say max depth.

13
00:00:45,010 --> 00:00:46,650
OK, Max Baptistery.

14
00:00:47,110 --> 00:00:50,700
So what is the what is the definition?

15
00:00:50,890 --> 00:00:57,640
So definition is basically the distance between the number of nodes, between the root node and the

16
00:00:57,640 --> 00:00:59,650
farthest node from the root.

17
00:00:59,680 --> 00:01:01,110
OK, I have to count.

18
00:01:01,330 --> 00:01:04,360
So four and five, so four and five.

19
00:01:05,080 --> 00:01:08,320
These are the farthest node from the root node.

20
00:01:09,460 --> 00:01:12,430
And what we will do, we will count the number of nodes between them.

21
00:01:12,910 --> 00:01:15,950
OK, so this is not one this is Nordal or against.

22
00:01:16,020 --> 00:01:18,010
This is not tree or this is also not tree.

23
00:01:18,500 --> 00:01:18,850
OK.

24
00:01:20,290 --> 00:01:26,920
Now for this military, what is the height or the maximum depth, so it is simply to this level one,

25
00:01:26,920 --> 00:01:29,290
this is level two, level one and level two.

26
00:01:29,620 --> 00:01:32,140
So the depth you can see is two.

27
00:01:32,950 --> 00:01:33,970
So I'm calling levels.

28
00:01:33,970 --> 00:01:38,050
You can say depth is one Baptista baptistery, OK?

29
00:01:39,150 --> 00:01:40,860
So now let us consider this example.

30
00:01:40,890 --> 00:01:47,130
So this is the root node, so this is that one, this is that two and this is that three.

31
00:01:47,370 --> 00:01:48,390
There is any other node.

32
00:01:48,420 --> 00:01:49,750
So this is that four.

33
00:01:50,130 --> 00:01:54,260
So the hide or you can say the maximum depth of this binary is basically four.

34
00:01:54,660 --> 00:01:56,090
Let's call it node five.

35
00:01:56,370 --> 00:01:58,320
So the depth or the height is four.

36
00:01:58,380 --> 00:01:58,740
OK.

37
00:02:00,080 --> 00:02:01,590
Now, let us consider this example.

38
00:02:01,620 --> 00:02:02,550
So this is the route north.

39
00:02:02,990 --> 00:02:09,800
So this is Daptone or you can say one depth to that three depth, four and five.

40
00:02:09,889 --> 00:02:13,700
OK, so six is the farthest north from the route node.

41
00:02:15,050 --> 00:02:20,300
And if you want to find out the height, what we will do, we will count the node to the node when this

42
00:02:20,300 --> 00:02:20,660
is No.

43
00:02:20,660 --> 00:02:21,060
Two.

44
00:02:21,110 --> 00:02:22,020
This is not three.

45
00:02:22,250 --> 00:02:23,270
This is not four.

46
00:02:23,270 --> 00:02:24,410
And this is node five.

47
00:02:24,590 --> 00:02:28,330
OK, so that's why the height is basically is five.

48
00:02:28,340 --> 00:02:31,040
Or you can say that makes Adap.tv makes Leptis five.

49
00:02:31,920 --> 00:02:34,670
OK, so I hope you understood the question.

50
00:02:35,610 --> 00:02:37,790
So basically, their definition is very simple.

51
00:02:39,340 --> 00:02:45,730
The maximum depth is basically the number of Naude along the longest path from the route to the farthest

52
00:02:45,730 --> 00:02:46,000
north.

53
00:02:46,030 --> 00:02:49,900
OK, so this is a little difficult to understand with the help of example.

54
00:02:49,900 --> 00:02:51,400
We can understand it inevitably.

55
00:02:51,460 --> 00:02:51,790
OK.

56
00:02:52,740 --> 00:02:59,040
Now, the question is, we are given a binary, OK, so the question is very simple.

57
00:02:59,040 --> 00:03:04,260
We are given a binary tree and we have to write the code for finding the maximum depth or you can see

58
00:03:04,260 --> 00:03:05,690
the height of the binary.

59
00:03:06,780 --> 00:03:08,630
So the function signature is very simple.

60
00:03:08,910 --> 00:03:14,010
It will be integer to the name of the function is eight and it will take root as input.

61
00:03:14,220 --> 00:03:14,580
OK.

62
00:03:15,660 --> 00:03:19,210
Now I have to write the code, so this is very simple.

63
00:03:19,980 --> 00:03:22,220
OK, so what I will do, very simple approach.

64
00:03:22,230 --> 00:03:25,490
This is Route A. This is the left subtree.

65
00:03:26,280 --> 00:03:27,660
This is the right subtree.

66
00:03:29,860 --> 00:03:36,220
OK, so what is the work of dysfunction hate, so this hate function takes root as input and it will

67
00:03:36,220 --> 00:03:38,090
return me the hate simple.

68
00:03:38,320 --> 00:03:41,320
So what I will do, find the height of the left subtree.

69
00:03:41,860 --> 00:03:43,850
Find the height of the eye.

70
00:03:43,870 --> 00:03:50,980
It's a pretty take the maximum of the height of the left and right subtree and add plus one.

71
00:03:50,980 --> 00:03:52,600
Right plus one because the root.

72
00:03:53,200 --> 00:03:57,800
OK, so what I will do I will find the height of the left separately.

73
00:03:58,030 --> 00:04:00,760
OK, so I will call this function height.

74
00:04:01,390 --> 00:04:03,740
I will give it rumold so sorry.

75
00:04:03,790 --> 00:04:04,540
Left subtree.

76
00:04:04,930 --> 00:04:10,960
So find the height of the left subtree then this height function will take right subtree.

77
00:04:10,960 --> 00:04:13,330
So it will return me the height of right subtree.

78
00:04:14,410 --> 00:04:18,190
And then after finding the height of Cyprien right.

79
00:04:18,550 --> 00:04:24,100
I will take the maximum of these two and I will add plus one plus one is due to rule.

80
00:04:25,160 --> 00:04:28,330
OK, let's take some example to understand it better be OK.

81
00:04:29,500 --> 00:04:31,540
So let us take some example.

82
00:04:33,620 --> 00:04:37,880
So suppose this is the tree for five, seven, six.

83
00:04:38,930 --> 00:04:40,780
Two and three.

84
00:04:41,620 --> 00:04:43,330
OK, so this is the root node.

85
00:04:44,880 --> 00:04:50,400
So what I'm saying here is find the height of the left debris, so the height of legs, approximately

86
00:04:50,400 --> 00:04:51,840
one, two, three.

87
00:04:52,030 --> 00:04:58,980
So the height of trees, one, find the height, the height of this tree, find the height of the right

88
00:04:58,980 --> 00:04:59,210
spot.

89
00:04:59,400 --> 00:05:02,480
So this is one depth one depth two.

90
00:05:02,790 --> 00:05:03,550
So this is two.

91
00:05:03,870 --> 00:05:08,370
OK, so four left subtree height is three four right subtree.

92
00:05:08,370 --> 00:05:09,240
The height is two.

93
00:05:09,430 --> 00:05:12,930
I will take the maximum of left side, left and right.

94
00:05:12,930 --> 00:05:13,180
Right.

95
00:05:13,200 --> 00:05:15,680
Which is basically three oak trees that then two.

96
00:05:15,990 --> 00:05:22,410
So three and I will add plus one plus one is due to not so it on several before.

97
00:05:22,490 --> 00:05:26,990
OK, you can see how good it is for forensics, the distance between them.

98
00:05:27,000 --> 00:05:29,670
So this is not one or two or three and four.

99
00:05:30,330 --> 00:05:32,180
OK, very simple approach.

100
00:05:33,000 --> 00:05:34,830
OK, this is very, very simple approach.

101
00:05:35,220 --> 00:05:41,040
Find the height of the left debris, find the height of the right subtree, take the maximum of them

102
00:05:41,040 --> 00:05:42,420
and add plus one.

103
00:05:43,910 --> 00:05:44,300
OK.

104
00:05:45,560 --> 00:05:49,320
Very, very simple, let us take one more example to understand it better.

105
00:05:49,340 --> 00:05:49,670
OK?

106
00:05:51,390 --> 00:05:58,410
Now, this is the example we need to find the height of the debris, so height of the trees, one,

107
00:05:58,770 --> 00:06:01,350
find the height of the right debris, which is zero.

108
00:06:01,770 --> 00:06:04,520
OK, you will take the maximum of one and zero.

109
00:06:04,530 --> 00:06:08,110
So it will be one and then I will add plus one due to the root node.

110
00:06:08,280 --> 00:06:12,690
So basically the height will be two four distri, which is correct.

111
00:06:13,170 --> 00:06:13,600
OK.

112
00:06:13,890 --> 00:06:15,000
So very, very simple.

113
00:06:16,130 --> 00:06:19,700
Mix of height of lift, height of right.

114
00:06:20,790 --> 00:06:26,700
I will take the maximum height of height of rights and I will add plus one, this plus one is due to

115
00:06:26,700 --> 00:06:28,320
root node, OK.

116
00:06:28,710 --> 00:06:29,370
Very simple.

117
00:06:29,880 --> 00:06:30,540
Understood.

118
00:06:30,720 --> 00:06:31,710
Now let's it called.

119
00:06:33,190 --> 00:06:35,500
OK, the name of the function is Max Depth.

120
00:06:36,520 --> 00:06:40,570
It is taking root as input and I have to return the hate or accept.

121
00:06:40,600 --> 00:06:42,820
OK, so first of all, the base.

122
00:06:43,390 --> 00:06:50,590
So if personal basically does not exist, OK, if the tree does not exist, then what will be the hate?

123
00:06:50,590 --> 00:06:53,200
The hate will be zero if it is not there.

124
00:06:53,380 --> 00:06:54,040
It will be zero.

125
00:06:54,040 --> 00:06:56,130
If they did not exist, it will be zero.

126
00:06:56,980 --> 00:06:59,500
Now let us find out the mix depth.

127
00:06:59,580 --> 00:07:03,010
You can say the height of the are so mixed depth.

128
00:07:04,810 --> 00:07:08,340
Give me the height of the left subtree.

129
00:07:08,380 --> 00:07:11,980
So now I know the max depth of the right of the left.

130
00:07:13,030 --> 00:07:16,750
Now let us try to find out the max depth of the.

131
00:07:20,640 --> 00:07:21,810
Right subtree, OK?

132
00:07:23,450 --> 00:07:29,780
So basically mixed tonight, the voters seem OK, they both seem so I'm writing here.

133
00:07:33,560 --> 00:07:36,410
Max, depth and height, they both have slim.

134
00:07:41,570 --> 00:07:48,500
So I know the extent of the legendary I know the height or the depth of the debris, but I have to do

135
00:07:48,500 --> 00:07:51,620
I have to take the maximum of these two and I have to add a plus one.

136
00:07:52,490 --> 00:07:55,250
So Mix's and build function in C++.

137
00:07:56,510 --> 00:08:04,110
The maximum of height of right, and you will let a person because of duty, road and Dritan.

138
00:08:04,200 --> 00:08:10,190
OK, so take the mics off left and right and add plus one and then return.

139
00:08:10,280 --> 00:08:10,610
OK.

140
00:08:14,790 --> 00:08:16,290
Now, let us our good.

141
00:08:20,420 --> 00:08:25,010
OK, so our code is working fine now let us right in our code on very small example.

142
00:08:28,290 --> 00:08:33,330
So let us take this example, one, two, three, and here I have four.

143
00:08:33,360 --> 00:08:35,039
OK, so what should be the answer?

144
00:08:35,070 --> 00:08:38,190
So I should be basically the height of this tree should be tree.

145
00:08:38,500 --> 00:08:39,870
OK, that makes dentistry.

146
00:08:40,230 --> 00:08:41,039
So what will happen?

147
00:08:42,169 --> 00:08:47,660
When when we call on left, give me the heart of the left, who will call on right to give me the right

148
00:08:47,660 --> 00:08:53,090
of their three will go on the left and basically left SNL, so it will return zero.

149
00:08:54,190 --> 00:08:55,580
Then three will call on, right?

150
00:08:55,600 --> 00:09:02,080
Give me the height of rights, so riot will return zero, then I will take the maximum of zero and zero,

151
00:09:02,410 --> 00:09:04,510
which is zero, and I will add plus one.

152
00:09:04,750 --> 00:09:08,510
OK, so three will return one to two.

153
00:09:09,190 --> 00:09:11,810
OK, so two colon left now.

154
00:09:11,820 --> 00:09:12,610
Two colon.

155
00:09:12,610 --> 00:09:12,940
Right.

156
00:09:13,420 --> 00:09:15,630
So give me the height of right height.

157
00:09:16,030 --> 00:09:17,640
Basically it will be right there.

158
00:09:17,780 --> 00:09:18,580
It does not exist.

159
00:09:18,790 --> 00:09:20,080
So it will return zero.

160
00:09:20,260 --> 00:09:22,020
OK, it will return zero.

161
00:09:22,720 --> 00:09:27,460
Then I have to take the mix off left subtree, which is one right subtree, which is zero.

162
00:09:27,610 --> 00:09:29,730
So one zero, which is maximum one.

163
00:09:29,980 --> 00:09:31,930
And I have to return one plus one.

164
00:09:31,990 --> 00:09:35,500
OK, so this two will return one.

165
00:09:36,540 --> 00:09:42,760
So it will return height to OK, no one has called on left, no one will call on right.

166
00:09:43,680 --> 00:09:47,070
Give me the height of right subtree forwell call left.

167
00:09:47,190 --> 00:09:48,180
Give me the height of Lurdes.

168
00:09:48,600 --> 00:09:49,910
Left separate does not exist.

169
00:09:49,920 --> 00:09:51,990
It will return zero to 10 zero.

170
00:09:52,410 --> 00:09:54,580
Then it will go on right right up.

171
00:09:54,630 --> 00:09:55,470
It does not exist.

172
00:09:55,470 --> 00:09:58,800
So it will return zero maximov zero zero.

173
00:09:58,800 --> 00:09:59,520
It will be zero.

174
00:09:59,790 --> 00:10:00,930
Then return plus one.

175
00:10:01,300 --> 00:10:02,250
OK Max.

176
00:10:02,430 --> 00:10:03,330
And plus one.

177
00:10:03,810 --> 00:10:05,130
So four will return when.

178
00:10:06,750 --> 00:10:12,220
To the root node now, root root node left is returning to right is returning one.

179
00:10:12,360 --> 00:10:14,980
So take the maximum of two and one, it will be two.

180
00:10:15,240 --> 00:10:18,350
So finally, it will return to plus one, which is three.

181
00:10:18,390 --> 00:10:20,350
OK, and three is our answer.

182
00:10:20,670 --> 00:10:22,410
So that's how this code is working.

183
00:10:22,440 --> 00:10:24,930
OK, now let's discuss the time complexity.

184
00:10:24,930 --> 00:10:27,210
Since we are going through each and every note time.

185
00:10:27,210 --> 00:10:29,040
Complexity is big often, OK.

186
00:10:30,440 --> 00:10:35,930
Very simple and similarly, the space complexity will be big, often in the worst case, OK, in the

187
00:10:35,930 --> 00:10:36,920
worst case, what will happen?

188
00:10:36,920 --> 00:10:40,970
Mitry is basically not a ballistically it is a one sided tree.

189
00:10:41,000 --> 00:10:44,820
OK, so suppose the tree is basically four, three and seven.

190
00:10:46,010 --> 00:10:47,240
So in this case, what will happen?

191
00:10:48,680 --> 00:10:53,780
So for will call on the left to find the right tree, will call on the left supplier to find out.

192
00:10:53,810 --> 00:11:00,130
So basically if there are three nodes in the military, so there are so the stakes will be three.

193
00:11:00,170 --> 00:11:03,920
OK, so that's why in the worst case, in the case of a good tree, OK.

194
00:11:05,550 --> 00:11:13,830
This is a good story, so so in the worst case, that is in the case of as good a tree, my time complexity

195
00:11:13,830 --> 00:11:14,850
will be big often.

196
00:11:14,880 --> 00:11:19,260
OK, so time and space, both are big often.

197
00:11:20,470 --> 00:11:26,020
And the code is very simple, only three to four lines of code, OK, only these three lines of code.

198
00:11:26,300 --> 00:11:26,570
OK.

199
00:11:28,100 --> 00:11:28,550
Thank you.

