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.