1
00:00:01,300 --> 00:00:01,960
Hi, everyone.

2
00:00:01,990 --> 00:00:07,360
So in this video, we are going to solve this question, find the least common ancestor, the short

3
00:00:07,390 --> 00:00:10,080
form is basically LTA, least common ancestor.

4
00:00:10,330 --> 00:00:15,880
So I have to find the least common ancestor of a best tree BSD, basically binary search tree.

5
00:00:16,059 --> 00:00:19,240
OK, so input will basically be three things.

6
00:00:19,690 --> 00:00:21,220
So first is the binary.

7
00:00:22,490 --> 00:00:23,760
And then two nods.

8
00:00:24,290 --> 00:00:31,640
OK, so three things will be input the military and two nodes, and we have to find the least common

9
00:00:31,640 --> 00:00:32,930
ancestor of these two nodes.

10
00:00:33,200 --> 00:00:36,350
OK, let us consider an example to understand the question.

11
00:00:36,380 --> 00:00:38,420
OK, so consider this military.

12
00:00:39,240 --> 00:00:40,610
OK, so this is a binary tree.

13
00:00:40,970 --> 00:00:41,650
What do you have to do?

14
00:00:41,660 --> 00:00:46,380
So let us first find out the least common ancestor of two nodes, then in 14.

15
00:00:46,430 --> 00:00:51,230
OK, so 10 in 14 either do not and we have to find the least common ancestor.

16
00:00:51,600 --> 00:00:53,580
OK, so this is 14.

17
00:00:53,600 --> 00:00:54,540
OK, this is 14.

18
00:00:55,340 --> 00:00:56,360
Now let us find out.

19
00:00:56,780 --> 00:00:58,910
So what are the ancestors often?

20
00:00:59,480 --> 00:01:04,700
So the ancestor of 10 is basically doing it and 20.

21
00:01:04,920 --> 00:01:06,770
OK, so ancestor of 10.

22
00:01:06,950 --> 00:01:13,660
So I'm writing here the ancestors of ten are basically 2L eight and twenty.

23
00:01:14,450 --> 00:01:16,440
Now what are the ancestors of 14?

24
00:01:16,700 --> 00:01:22,220
So the ancestors of 14 are basically twenty eight and 20.

25
00:01:22,250 --> 00:01:25,480
OK, well eight and 20.

26
00:01:25,820 --> 00:01:32,240
So what we have to do so I have to find first the common and least it should be standard, should be

27
00:01:32,240 --> 00:01:32,660
common.

28
00:01:32,660 --> 00:01:35,660
So 2L is the least and it is the common OK.

29
00:01:36,630 --> 00:01:41,580
So 2L is basically the lowest common, least common ancestor of 10 and 14.

30
00:01:42,270 --> 00:01:44,220
OK, so I hope you understand.

31
00:01:44,820 --> 00:01:48,280
OK, so 2L is the least common ancestor of 10 and 14.

32
00:01:48,880 --> 00:01:50,720
Now let us consider it N14.

33
00:01:51,720 --> 00:01:53,430
OK, so basically.

34
00:01:54,390 --> 00:02:02,100
Let us find out the least common ancestor of it, and 14 so far, it basically the node itself is also

35
00:02:02,110 --> 00:02:02,640
ancestor.

36
00:02:02,670 --> 00:02:03,690
So this is it.

37
00:02:03,690 --> 00:02:05,200
And twenty by the definition.

38
00:02:05,220 --> 00:02:06,330
OK, and 414.

39
00:02:06,900 --> 00:02:07,770
So 414.

40
00:02:07,770 --> 00:02:08,990
This is basically 12.

41
00:02:09,240 --> 00:02:11,400
And then we have eight and then we have 20.

42
00:02:11,400 --> 00:02:12,690
OK, so eight is the common.

43
00:02:13,780 --> 00:02:16,260
So basically, the output for this is basically eight.

44
00:02:17,050 --> 00:02:19,540
OK, now consider this example.

45
00:02:21,030 --> 00:02:21,600
So this is a.

46
00:02:23,070 --> 00:02:25,060
This is also about, OK.

47
00:02:25,770 --> 00:02:26,700
Both are bisdee.

48
00:02:27,750 --> 00:02:33,450
Now, let us find out the least common ancestor of 28, Cerveris, too, so this is true and this is

49
00:02:33,450 --> 00:02:33,620
it.

50
00:02:33,810 --> 00:02:38,580
So least common ancestor is now let's find out the last common ancestor of two and four.

51
00:02:38,580 --> 00:02:40,590
So this is two and this is four.

52
00:02:40,750 --> 00:02:42,930
So the least common ancestor is to itself.

53
00:02:43,350 --> 00:02:47,280
OK, now let us find out the least common ancestor of.

54
00:02:48,230 --> 00:02:51,300
Let's say seven and nine, so for seven and nine, it will be eight.

55
00:02:51,680 --> 00:02:53,480
OK, so this is seven and this is nine.

56
00:02:53,480 --> 00:02:55,160
So last common ancestor, is it?

57
00:02:55,940 --> 00:03:00,530
OK, now let's find out the least common ancestor of basically zero and seven.

58
00:03:01,000 --> 00:03:05,570
OK, so basically this is zero and this is seven.

59
00:03:05,580 --> 00:03:07,700
So the lowest common ancestor is basically six.

60
00:03:08,390 --> 00:03:10,520
OK, so at least a common ancestor is six.

61
00:03:11,920 --> 00:03:14,080
But really, the least common ancestor of.

62
00:03:15,180 --> 00:03:17,170
Let's say three and zero.

63
00:03:17,250 --> 00:03:22,110
OK, so four, three and zero, the last common ancestor is basically two.

64
00:03:22,710 --> 00:03:24,480
OK, so the least common ancestor is two.

65
00:03:25,500 --> 00:03:31,620
Now, what will be the least common ancestor of basically zero and nine, so this is zero.

66
00:03:32,010 --> 00:03:32,790
This is nine.

67
00:03:32,790 --> 00:03:34,560
So lowest common ancestor is six.

68
00:03:35,410 --> 00:03:39,630
OK, so now I hope you understood what is the meaning of least common ancestor.

69
00:03:39,810 --> 00:03:46,740
OK, so the input will be two things first observed by necessity and then the two nodes and we have

70
00:03:46,740 --> 00:03:48,900
to find the earliest common ancestor.

71
00:03:49,900 --> 00:03:50,290
OK.

72
00:03:51,920 --> 00:03:53,930
Now, let's see how we can solve this question.

73
00:03:54,120 --> 00:03:57,000
OK, so let us consider this example.

74
00:03:57,000 --> 00:03:59,180
So let's say twenty eight, 22.

75
00:03:59,180 --> 00:04:02,960
So I have to consider a OK, because in the question is given.

76
00:04:02,990 --> 00:04:03,680
So this is a.

77
00:04:04,550 --> 00:04:05,860
OK, so this is a beast.

78
00:04:06,170 --> 00:04:12,080
And let's say I have to find basically the least common ancestor of tuners and let the two nodes, 13

79
00:04:12,080 --> 00:04:12,650
and 14.

80
00:04:13,340 --> 00:04:14,920
So the logic is very, very simple.

81
00:04:15,290 --> 00:04:17,700
What we will do, we will try to find out these nodes.

82
00:04:18,380 --> 00:04:24,710
So the main idea, the main idea behind the main idea to solve this question is basically find node.

83
00:04:26,210 --> 00:04:27,200
So this is the idea.

84
00:04:27,250 --> 00:04:31,940
OK, so we have to find Bernard, so let us start finding the A..

85
00:04:31,970 --> 00:04:34,270
OK, so how we can find a..

86
00:04:34,280 --> 00:04:36,010
Basically, I will start from the root node.

87
00:04:36,710 --> 00:04:37,760
So this is the root node.

88
00:04:39,440 --> 00:04:44,510
Now, the input is basically about so compared to 20 with Ben and 14.

89
00:04:45,580 --> 00:04:52,050
OK, so 20 is basically good, then 10 and 20 is basically good, then 14.

90
00:04:52,510 --> 00:04:57,400
So obviously to find out the ten, I have to go in the left hand side and obviously to find out the

91
00:04:57,400 --> 00:05:01,470
14, I have to go in the left hand side because the given is basically bisdee.

92
00:05:01,870 --> 00:05:03,790
And for Steve, this is the root node.

93
00:05:04,000 --> 00:05:06,410
So that's more level usually present in the left hand side.

94
00:05:06,460 --> 00:05:11,040
OK, so that's why if I want to find out then because the idea is find the nodes.

95
00:05:11,260 --> 00:05:14,050
So if you want to find then go in the left hand side.

96
00:05:14,260 --> 00:05:17,290
If you want to find the 14, then also go in the left hand side.

97
00:05:17,830 --> 00:05:19,740
So now let's go to the left hand side.

98
00:05:19,750 --> 00:05:21,470
So at the left hand side I have it.

99
00:05:21,850 --> 00:05:23,310
So now let's compare again.

100
00:05:23,530 --> 00:05:25,420
So it is basically less than 10.

101
00:05:27,050 --> 00:05:29,240
And it is basically less than 14.

102
00:05:30,110 --> 00:05:34,970
OK, so now in this case, what will happen in order to find out, then I will go in the right hand

103
00:05:34,970 --> 00:05:36,940
side in order to find out 14.

104
00:05:36,950 --> 00:05:40,490
I will go in the right hand side because this is a BSD and investee.

105
00:05:40,500 --> 00:05:44,030
If this is the root node, then the larger value will lie in the right hand side.

106
00:05:44,280 --> 00:05:46,730
OK, so now let's go to the right hand side.

107
00:05:46,970 --> 00:05:48,670
So right hand side is basically equal.

108
00:05:48,910 --> 00:05:51,030
OK, so now we will compare tool.

109
00:05:51,950 --> 00:05:58,460
So basically Google is basically good dentin and well is basically less than 14.

110
00:05:59,030 --> 00:06:00,980
OK, so in this case, what is the scenario?

111
00:06:00,980 --> 00:06:04,040
In order to find out, then you have to go in the left hand side.

112
00:06:05,240 --> 00:06:11,240
OK, in order to find 14, you have to go in the right hand side, OK, so here we have a contradiction.

113
00:06:11,650 --> 00:06:19,280
OK, so this condition is this condition is go in the left hand side and this condition is telling me

114
00:06:19,280 --> 00:06:20,600
to go in the right hand side.

115
00:06:20,810 --> 00:06:21,800
So where should I go?

116
00:06:22,070 --> 00:06:24,270
So the answer is basically do not go anywhere.

117
00:06:24,410 --> 00:06:25,550
My answer will be to.

118
00:06:26,630 --> 00:06:31,400
OK, my answer will be equal, so that logic is very simple whenever you have a contradiction.

119
00:06:31,400 --> 00:06:34,530
So should I go in the left hand side or should I go in the right hand side?

120
00:06:34,550 --> 00:06:36,850
So you have a contradiction with every contradiction.

121
00:06:37,190 --> 00:06:39,550
So obviously that the truth is your answer.

122
00:06:39,560 --> 00:06:46,750
So you can see the L.C of 10 and 14 Daltry often in 14 is basically equal and is my answer.

123
00:06:47,740 --> 00:06:48,610
Very, very simple.

124
00:06:49,300 --> 00:06:53,070
OK, you got the logic, so let us consider one more example.

125
00:06:53,110 --> 00:07:00,640
OK, now suppose you want to find out the LCA of, let's say, 1814.

126
00:07:02,510 --> 00:07:05,050
So basically all of 1814, is it only.

127
00:07:05,260 --> 00:07:07,470
OK, now let us follow this logic.

128
00:07:07,480 --> 00:07:11,620
So the idea is basically find out Donald's idea is very simple.

129
00:07:11,690 --> 00:07:14,830
OK, so I will start with 20.

130
00:07:14,830 --> 00:07:21,790
I will start finding from the root node, so to David it so 26 it guarantees then 14.

131
00:07:21,800 --> 00:07:27,280
So this condition stays go left in order to find out that this condition says go left in order to find

132
00:07:27,280 --> 00:07:27,840
out 14.

133
00:07:27,850 --> 00:07:28,760
So I will go left.

134
00:07:29,140 --> 00:07:31,230
So if I will go left, I have it.

135
00:07:31,420 --> 00:07:33,520
OK, so compare it.

136
00:07:33,700 --> 00:07:37,180
So it guerdon it and then the second condition is eight.

137
00:07:37,180 --> 00:07:38,000
Guerdon 14.

138
00:07:38,680 --> 00:07:42,970
OK, so basically in this situation, so this condition is telling me to go right.

139
00:07:44,290 --> 00:07:46,180
And this condition is basically false.

140
00:07:46,360 --> 00:07:48,900
OK, so this condition is basically false.

141
00:07:51,310 --> 00:07:56,320
So what you can do in this case also, I would honestly, I will stop, OK, so in this condition also

142
00:07:56,320 --> 00:07:56,980
I will stop.

143
00:07:59,120 --> 00:08:03,440
Because this condition is false, it is not guarded, so where should I go?

144
00:08:04,250 --> 00:08:07,640
OK, so what I will do basically it is it goes to it.

145
00:08:07,670 --> 00:08:12,560
So whenever you will find out the node, whenever you will reach one of the nodes, you will stop and

146
00:08:12,560 --> 00:08:13,840
the answer will be it only.

147
00:08:14,370 --> 00:08:16,500
OK, so there are two conditions to stop.

148
00:08:16,520 --> 00:08:21,440
First, when there is a contradiction and the second condition to stop is basically when you find out

149
00:08:21,440 --> 00:08:24,950
any one of that would OK when you reach any one of the two nodes.

150
00:08:25,100 --> 00:08:27,020
So in this case, I reached it.

151
00:08:27,200 --> 00:08:28,250
I reached Noraid.

152
00:08:28,250 --> 00:08:29,050
So I will stop.

153
00:08:29,330 --> 00:08:30,350
So I will stop.

154
00:08:31,520 --> 00:08:33,370
OK, so very, very simple.

155
00:08:33,860 --> 00:08:35,659
We just have to find out the nodes.

156
00:08:36,780 --> 00:08:41,850
OK, now, basically in discussion, discussion, we have an assumption, OK, what is the assumption?

157
00:08:42,240 --> 00:08:47,820
So assumption is basically that given to NATO military that donors are present in.

158
00:08:48,180 --> 00:08:49,280
So this is the assumption.

159
00:08:49,380 --> 00:08:52,600
Now, let us take one more example to understand it in a better way.

160
00:08:52,650 --> 00:08:52,980
OK.

161
00:08:55,710 --> 00:08:57,150
So let us take this example.

162
00:08:59,080 --> 00:09:05,410
OK, let us take this example and we have to find out the energy of 200 l.c after one year to start

163
00:09:05,410 --> 00:09:05,900
with six.

164
00:09:06,730 --> 00:09:10,680
So six is good, then to six is basically less than eight.

165
00:09:10,990 --> 00:09:14,710
So in order to find out, do I have to go in the left hand side in order to find out?

166
00:09:14,710 --> 00:09:16,410
Did I have to go in the right hand side?

167
00:09:16,420 --> 00:09:19,900
So whenever there's a contraction, we will stop and our answer will be six.

168
00:09:20,240 --> 00:09:22,230
OK, so six is my answer.

169
00:09:22,240 --> 00:09:24,680
You can see six is my answer.

170
00:09:25,240 --> 00:09:33,280
OK, now let us try to find out the LTA of basically let's take zero and three, OK, zero entry.

171
00:09:33,290 --> 00:09:36,130
So I have to find the LC of zero entry.

172
00:09:36,880 --> 00:09:40,390
So my answer should be to OK, my answer should be to Lalaji.

173
00:09:40,900 --> 00:09:42,070
So I will start with six.

174
00:09:42,580 --> 00:09:44,050
So six is basically good then.

175
00:09:44,080 --> 00:09:44,410
Zero.

176
00:09:44,410 --> 00:09:46,000
Six is basically good then three.

177
00:09:46,010 --> 00:09:46,810
So go left.

178
00:09:47,080 --> 00:09:49,030
Discretional also says go left.

179
00:09:49,420 --> 00:09:53,420
So if I will go left I have to now two is basically greater than zero.

180
00:09:53,440 --> 00:09:57,240
So in order to find out zero go left, two is basically less than three.

181
00:09:57,250 --> 00:09:59,200
So in order to find out three go right.

182
00:09:59,370 --> 00:10:00,810
OK, so there is a contradiction.

183
00:10:00,820 --> 00:10:03,950
So my answer is basically to OK, so two is the right answer.

184
00:10:04,840 --> 00:10:06,390
So I hope you understood the logic.

185
00:10:06,880 --> 00:10:07,690
Now, one more thing.

186
00:10:07,900 --> 00:10:09,820
I told you so basically.

187
00:10:11,680 --> 00:10:16,000
What they have to do is basically be in the tunnels and they exist in the body.

188
00:10:16,030 --> 00:10:16,330
OK.

189
00:10:16,360 --> 00:10:17,970
So this is the assumption of the question.

190
00:10:18,460 --> 00:10:24,310
So this is basically the assumption of the question that both then would be in Cuba does not exist in

191
00:10:24,310 --> 00:10:24,820
that tree.

192
00:10:24,890 --> 00:10:28,290
OK, so if this assumption is not there, then what we have to do.

193
00:10:28,480 --> 00:10:33,370
So first of all, we have to find whether the boat the not exist in a tree or not.

194
00:10:33,400 --> 00:10:40,030
OK, so if the assumption is not there, if the assumption is not there, my first step is basically

195
00:10:40,030 --> 00:10:40,720
what we have to do.

196
00:10:40,720 --> 00:10:44,770
So in the first step, I will check whether the nodes are present in that tree or not.

197
00:10:44,800 --> 00:10:50,450
OK, so if the nodes are not present in the tree, so if any of the node, if any of the two nodes.

198
00:10:50,590 --> 00:10:56,870
So if any of the two nodes are not present in that tree, then this question is basically invalid question.

199
00:10:57,370 --> 00:11:02,410
OK, this question is invalid question because we have to find the least common ancestor of two nodes,

200
00:11:02,980 --> 00:11:04,300
B and Q, other two node.

201
00:11:04,300 --> 00:11:06,260
So both and also the existing debris.

202
00:11:06,910 --> 00:11:11,810
Otherwise this question is basically invalid question because LC will not exist.

203
00:11:11,860 --> 00:11:16,720
OK, the common ancestor will not exist if any of the two nodes are not present in the tree.

204
00:11:17,020 --> 00:11:19,420
OK, so first step is basically very simple.

205
00:11:19,430 --> 00:11:22,240
We have to check whether two NATO is in a tree or not.

206
00:11:22,430 --> 00:11:25,980
OK, but the question it is that do not will always be present in the tree.

207
00:11:26,410 --> 00:11:28,120
So we do not have to check this condition.

208
00:11:28,120 --> 00:11:29,560
We can directly write our code.

209
00:11:29,600 --> 00:11:32,090
OK, so now let's write the code.

210
00:11:32,110 --> 00:11:33,970
So writing code, very, very simple.

211
00:11:34,600 --> 00:11:38,340
So what I have to do, so I have to write to the condition.

212
00:11:38,360 --> 00:11:41,350
So what I will do, I will compare but that I have to go left or right.

213
00:11:41,380 --> 00:11:44,890
So if raw data is basically good then so be encoder to node.

214
00:11:44,920 --> 00:11:52,780
OK, I have to find that LC of two nodes which are Banku, so if it is a good then B and basically the

215
00:11:52,780 --> 00:11:59,140
root data is also good, then that means in order to find out Banku I have to go left.

216
00:11:59,350 --> 00:12:01,330
OK, so for going left I can write.

217
00:12:01,780 --> 00:12:03,520
Rudik was left off route.

218
00:12:04,030 --> 00:12:04,570
Simple.

219
00:12:04,960 --> 00:12:11,260
Now the second condition will be so if the root data is basically less then B and similarly, if the

220
00:12:11,260 --> 00:12:18,580
root data is basically less then Q Then in order to find out, in order to find out B and do what I

221
00:12:18,580 --> 00:12:18,970
have to do.

222
00:12:18,970 --> 00:12:19,600
So I have to go.

223
00:12:19,600 --> 00:12:19,970
Right.

224
00:12:19,990 --> 00:12:21,780
So in order to go right, what I will write.

225
00:12:22,180 --> 00:12:25,510
So I will write a root cause right of root.

226
00:12:25,810 --> 00:12:29,020
And in the third condition basically there will be conflict.

227
00:12:29,080 --> 00:12:32,060
OK, so here root data is good then B and good.

228
00:12:32,080 --> 00:12:36,960
Then you hear the raw data is less than B and left in the third case, the conflict.

229
00:12:37,090 --> 00:12:43,570
And if there is a conflict, so in the third condition, the L Spartacists or if in the end if part

230
00:12:43,570 --> 00:12:44,790
and this is the end.

231
00:12:44,980 --> 00:12:47,930
So in the conflict in the elzbieta there will be conflict.

232
00:12:47,950 --> 00:12:53,540
So whenever there's a conflict we can stop and we can return to OK, we can return root.

233
00:12:53,950 --> 00:12:54,440
Simple.

234
00:12:55,000 --> 00:12:57,350
So this is basically a data solution.

235
00:12:57,430 --> 00:13:00,340
OK, this is basically iterative solution.

236
00:13:00,490 --> 00:13:02,170
There's no need for decoration here.

237
00:13:02,230 --> 00:13:04,060
OK, so now let's write the code.

238
00:13:06,350 --> 00:13:09,470
So basically, what is certain types of return type is old style.

239
00:13:09,530 --> 00:13:14,270
OK, so in this case for 2008, when I I'm returning, I am returning six.

240
00:13:14,300 --> 00:13:20,540
So six is basically I do not start OK, so I have to return North Star and be you also also.

241
00:13:21,320 --> 00:13:22,790
OK, so what I have to do.

242
00:13:23,390 --> 00:13:24,970
So I have to search for Nords.

243
00:13:25,100 --> 00:13:25,880
OK, so.

244
00:13:26,870 --> 00:13:34,790
Wildwood is not a ghost tunnel, so Wildwood is not in first condition, so if Rudy down, so I'm using

245
00:13:34,790 --> 00:13:36,830
this condition, OK, this first condition.

246
00:13:38,900 --> 00:13:43,070
So basically, if the root value is greater than the value.

247
00:13:50,080 --> 00:13:57,940
So if you'd value is lower than the value of P and the root value is basically greater than the value

248
00:13:57,940 --> 00:13:58,420
of Q.

249
00:14:00,010 --> 00:14:00,880
So in this case.

250
00:14:02,360 --> 00:14:04,770
And I to find out, you have to go left.

251
00:14:04,790 --> 00:14:09,860
So let us go left simple now in the elusive condition.

252
00:14:12,790 --> 00:14:14,020
So basically, if the.

253
00:14:15,010 --> 00:14:17,440
Route value is less than P-value.

254
00:14:19,510 --> 00:14:22,900
And root value is less than.

255
00:14:24,770 --> 00:14:25,450
Q Value.

256
00:14:26,830 --> 00:14:30,010
Then in order to find out Banku, you have to go, right?

257
00:14:30,040 --> 00:14:32,950
OK, so basically Rootes route, is it closed?

258
00:14:32,960 --> 00:14:33,430
All right.

259
00:14:33,430 --> 00:14:33,880
Off route.

260
00:14:36,120 --> 00:14:41,250
Simple now in the Elzbieta is conflict, whether I should go left or whether I should go right.

261
00:14:41,430 --> 00:14:45,840
So in the last part you will stop and you will return the answer, which is it would only OK.

262
00:14:46,720 --> 00:14:48,550
Now, in order for the completion purposes.

263
00:14:48,580 --> 00:14:50,780
OK, so I have to return it in order.

264
00:14:51,130 --> 00:14:55,760
So for the completion purpose, I have to return something here.

265
00:14:55,810 --> 00:14:57,320
OK, so let's get it done here.

266
00:14:57,640 --> 00:15:00,400
So again, this line will never get executed.

267
00:15:00,430 --> 00:15:02,890
OK, this line will never get executed.

268
00:15:02,950 --> 00:15:05,570
This is only for the completion purposes.

269
00:15:05,590 --> 00:15:09,140
OK, so this line is important only for completion purposes.

270
00:15:09,160 --> 00:15:10,770
This line will never get executed.

271
00:15:12,970 --> 00:15:15,650
OK, so this is the computer code, very simple code.

272
00:15:15,830 --> 00:15:18,100
OK, so compare the root value.

273
00:15:19,150 --> 00:15:21,270
So this is basically this one.

274
00:15:21,280 --> 00:15:28,030
OK, so compare the root value with the value of P and similarly compare the root value with a value.

275
00:15:28,930 --> 00:15:34,870
OK, so both Benguela in the left to go left in this case, both be in line, the right to go right

276
00:15:35,110 --> 00:15:37,220
in the part this conflict so you can return.

277
00:15:37,540 --> 00:15:40,780
Now first we will run our court and then we will try to submit our call.

278
00:15:40,820 --> 00:15:41,170
OK.

279
00:15:45,220 --> 00:15:45,820
Now, there are some.

280
00:15:49,790 --> 00:15:51,050
OK, let's meet again.

281
00:15:56,150 --> 00:15:57,880
OK, guess clavichord is working fine.

282
00:15:59,000 --> 00:16:01,790
Neither does discuss their time and the space complexity.

283
00:16:02,630 --> 00:16:06,320
OK, so basically these are the two conditions.

284
00:16:07,560 --> 00:16:11,660
And this is the conflict, OK, whether I should go left or whether I should go right.

285
00:16:12,780 --> 00:16:14,280
Now, what is the space complexity?

286
00:16:14,670 --> 00:16:16,340
So this is the iterative version.

287
00:16:16,400 --> 00:16:21,820
OK, so we are using it to we are traversing the tree in the outer division.

288
00:16:21,840 --> 00:16:25,290
OK, so the space complexity is big off when we are not using any stick.

289
00:16:26,290 --> 00:16:31,330
Now, what would be the time, complexity, time, complexity is big often, so this is wrong.

290
00:16:31,570 --> 00:16:36,340
This is not because we are not going through each and every node so -- complex it is.

291
00:16:36,340 --> 00:16:37,890
Basically we go off edge.

292
00:16:38,650 --> 00:16:41,380
So what is Hetch Hetchy is basically the height of the tree.

293
00:16:42,920 --> 00:16:44,710
That is basically the height of the tree.

294
00:16:46,070 --> 00:16:47,510
OK, so this is wrong.

295
00:16:48,280 --> 00:16:52,580
I'm going back to this big often only when you are going through each and every node, but in this case,

296
00:16:52,580 --> 00:16:54,650
you can see carefully at each line.

297
00:16:54,740 --> 00:16:56,000
I am taking the condition.

298
00:16:56,180 --> 00:17:00,410
I am taking a data situation whether you should go left or whether you should go right.

299
00:17:00,510 --> 00:17:02,480
OK, so if this is the three letter.

300
00:17:03,730 --> 00:17:04,829
So this is the Fruitland.

301
00:17:06,880 --> 00:17:13,240
So at each node, I am taking the condition whether I should go left, I am digging, I am taking a

302
00:17:13,240 --> 00:17:15,790
decision whether I should go left or whether I should go right.

303
00:17:15,819 --> 00:17:22,000
OK, so suppose first I go left, then I go right, then again I go left.

304
00:17:22,190 --> 00:17:23,910
Then let's say I go right.

305
00:17:23,920 --> 00:17:26,079
And then finally here I will stop.

306
00:17:26,619 --> 00:17:32,220
OK, so basically what I am doing in the worst case, I will reach here, I will reach the lymph node.

307
00:17:32,710 --> 00:17:34,420
This will be the worst case, ok.

308
00:17:35,410 --> 00:17:40,850
So basically the height of the trees, let's call it the height of the trees five, so this note is

309
00:17:40,870 --> 00:17:42,480
present at depth five.

310
00:17:42,490 --> 00:17:45,730
So I will reach in the worst case, I will reach this height.

311
00:17:45,760 --> 00:17:49,810
OK, so what is happening here is at each node.

312
00:17:50,960 --> 00:17:55,910
At eight a.m., taking the decision whether I should go left or whether I should go right, you can

313
00:17:55,910 --> 00:17:56,660
see yourself.

314
00:17:56,850 --> 00:18:00,240
I am taking a decision whether I should go left or whether I should go right.

315
00:18:00,260 --> 00:18:02,990
OK, so I am not going through each and every node.

316
00:18:03,170 --> 00:18:08,320
So that's why this is the wrong time complexity and this is the correct time complexity.

317
00:18:08,330 --> 00:18:12,320
OK, big off Hetch Hetchy is basically the height of the.

318
00:18:15,010 --> 00:18:19,810
OK, because at every note, I have to take a decision whether I should go left or whether I should

319
00:18:19,810 --> 00:18:20,320
go right.

320
00:18:20,540 --> 00:18:24,010
OK, so finally, time complexities, big off edge.

321
00:18:24,490 --> 00:18:26,560
Where is the height and the space complexities?

322
00:18:26,560 --> 00:18:27,310
Big off one.

323
00:18:27,620 --> 00:18:28,020
OK.

324
00:18:30,180 --> 00:18:33,480
So if you have any doubt in this question, you can ask me, OK, thank you.

