1 00:00:00,930 --> 00:00:02,460 Hi, everyone, welcome back. 2 00:00:02,490 --> 00:00:07,490 So in this video, we are going to write the code for this problem, but before writing the code, let's 3 00:00:07,500 --> 00:00:17,370 first it is our screen and let us summarize all these four conditions, all these four cases, and then 4 00:00:17,370 --> 00:00:19,100 we can start writing the code. 5 00:00:19,110 --> 00:00:19,500 Fine. 6 00:00:20,220 --> 00:00:27,690 So what we are going to do here is so first let me write here that the first cases, if the left is 7 00:00:27,690 --> 00:00:30,390 null, write this one if left and right. 8 00:00:31,200 --> 00:00:34,710 So if left is null, write is also null. 9 00:00:36,040 --> 00:00:42,490 Then we discussed that Banku not found, so if not found the lowest common Chesterville, obviously 10 00:00:42,490 --> 00:00:42,750 none. 11 00:00:42,820 --> 00:00:45,010 So my answer will be then I will return an. 12 00:00:46,760 --> 00:00:54,290 The second case is basically left seasonal right to second guess is your left is. 13 00:00:55,250 --> 00:01:01,760 So in that case, whatever value you are getting from the right Sabry, you are returning that value, 14 00:01:01,790 --> 00:01:02,110 right. 15 00:01:02,420 --> 00:01:06,260 So left and right is not null. 16 00:01:07,490 --> 00:01:11,380 So in this case, your answer will be right. 17 00:01:11,430 --> 00:01:12,830 This is the answer. 18 00:01:14,390 --> 00:01:22,980 Tardigrades can be left is normal when you are the left hand side and right is null in not present in 19 00:01:23,000 --> 00:01:23,750 the right subtree. 20 00:01:24,050 --> 00:01:28,450 So in that case, my lowest common ancestor will be whatever value I am getting from the left subtree. 21 00:01:28,520 --> 00:01:30,350 That will be the lowest common ancestor. 22 00:01:30,740 --> 00:01:35,540 So I will be left for TKIs can be left and right both exist. 23 00:01:35,540 --> 00:01:38,930 So left is not null, right is also not null. 24 00:01:39,110 --> 00:01:40,710 Both values at present. 25 00:01:40,720 --> 00:01:46,190 That means one of the node is laying in the left subtree and another node is laying in the right sempre. 26 00:01:46,400 --> 00:01:49,520 So that is the definition of lowest common ancestor. 27 00:01:49,550 --> 00:01:54,450 So in that case, my answer will be ruled itself fine. 28 00:01:54,920 --> 00:02:00,230 So now let's remove all this and now we can start writing the code. 29 00:02:04,870 --> 00:02:12,940 So being other two nodes and we need to find out the lowest common ancestor for these two nodes and 30 00:02:12,940 --> 00:02:15,070 we have discussed all the recursive cases. 31 00:02:15,850 --> 00:02:20,210 So now let's start writing the code to first of all basis. 32 00:02:20,770 --> 00:02:22,030 So what will we base case? 33 00:02:22,030 --> 00:02:26,140 Base case will be if your tree does not exist, right. 34 00:02:26,560 --> 00:02:31,330 So if tree does not exist, then what will be your lowest common ancestor? 35 00:02:31,330 --> 00:02:35,320 Obviously null lowest common ancestor will not exist. 36 00:02:37,000 --> 00:02:37,450 Right. 37 00:02:37,690 --> 00:02:42,520 And now we discussed that if root is itself. 38 00:02:43,380 --> 00:02:50,140 Is it going to be or root is equal to. 39 00:02:52,180 --> 00:02:56,040 Q So in that case, what will be the lowest common ancestor. 40 00:02:56,050 --> 00:02:56,230 What. 41 00:02:56,410 --> 00:02:56,950 My answer. 42 00:02:56,980 --> 00:02:59,310 My answer will be root itself. 43 00:02:59,320 --> 00:02:59,710 Right. 44 00:02:59,740 --> 00:03:07,260 We have discussed this otherwise, but we need to do we need to search in left and right. 45 00:03:07,720 --> 00:03:09,410 So this is left. 46 00:03:10,360 --> 00:03:14,050 What I will do, I will call the function lowest common ancestor. 47 00:03:17,180 --> 00:03:20,750 And I will give them their subtree. 48 00:03:23,190 --> 00:03:32,280 B and Q search B and given level, and similarly, I will do the opposite for this, I will also call 49 00:03:32,280 --> 00:03:37,640 on the right Sabry because this is not bisdee, so it cannot decide in which direction you can go. 50 00:03:38,040 --> 00:03:43,260 So you need to go in both the direction and try to search for P and Q wait. 51 00:03:44,990 --> 00:03:52,820 So I'm searching for Bianca in the subtree as well as in the right subtree, fine, and now we discussed 52 00:03:52,820 --> 00:03:53,680 four cases. 53 00:03:53,960 --> 00:03:55,920 So first case is very simple. 54 00:03:56,300 --> 00:04:03,260 So if left personal and so this is left not. 55 00:04:03,260 --> 00:04:05,060 And this is left. 56 00:04:08,870 --> 00:04:12,650 So if left is null and 57 00:04:15,680 --> 00:04:16,790 void is also null. 58 00:04:19,200 --> 00:04:21,339 So we discussed that my answer will be none. 59 00:04:22,019 --> 00:04:24,340 So what I'm going to return, I will return. 60 00:04:26,890 --> 00:04:30,550 The second case was, so this is Altaf. 61 00:04:33,820 --> 00:04:42,220 And if left is null, left is null and void is not an all right exist. 62 00:04:44,850 --> 00:04:52,650 So in that case, we discussed that my answer will be right, so I will return right Tariq cases. 63 00:04:54,800 --> 00:05:01,820 Left is not null and riot is null. 64 00:05:02,570 --> 00:05:10,520 So in that case, we discussed that our answer will be left and it finally fought case enfold case. 65 00:05:10,520 --> 00:05:11,750 My answer is rude. 66 00:05:11,760 --> 00:05:13,640 So let's directly return route. 67 00:05:14,840 --> 00:05:18,080 And that said, very simple court. 68 00:05:18,080 --> 00:05:18,470 Right. 69 00:05:18,920 --> 00:05:20,180 Let's test our code. 70 00:05:24,620 --> 00:05:25,700 Yep, now a little. 71 00:05:29,350 --> 00:05:36,620 So, yeah, our goal is right, our goal past all the test cases and you can see this is very simple. 72 00:05:36,700 --> 00:05:37,230 All right. 73 00:05:37,990 --> 00:05:42,400 And what we can do, we can write in our code on one of the examples given indication. 74 00:05:43,030 --> 00:05:45,760 So which example we should pick? 75 00:05:47,020 --> 00:05:48,490 Let's pick this one. 76 00:05:48,580 --> 00:05:48,970 Right. 77 00:05:49,690 --> 00:05:52,270 And let's try to understand how the code will work. 78 00:05:52,840 --> 00:05:56,980 So the value of B is five and the value of Q is four. 79 00:05:57,080 --> 00:05:59,170 OK, so I will stand here. 80 00:05:59,500 --> 00:06:05,500 I will compare the three is not close to five and four, so I will go in the left right now with five. 81 00:06:05,530 --> 00:06:07,390 So five equals five, right. 82 00:06:07,720 --> 00:06:08,820 Five equals five. 83 00:06:08,830 --> 00:06:09,730 We will hit this. 84 00:06:09,940 --> 00:06:11,800 In that case I'm going to return. 85 00:06:12,130 --> 00:06:13,270 So I will return five. 86 00:06:16,190 --> 00:06:20,880 Right now from left, I got the answer, now I will call on, right. 87 00:06:21,140 --> 00:06:25,790 So check for so when is not close to five and four. 88 00:06:26,660 --> 00:06:29,870 Zero is not close to five and four zero will call on left. 89 00:06:29,880 --> 00:06:32,480 It will get nine zero will call on right. 90 00:06:32,480 --> 00:06:33,560 It will get nine. 91 00:06:33,830 --> 00:06:37,760 And whenever we are getting help from both sides I will return. 92 00:06:38,150 --> 00:06:41,390 So zero will return and then one will call on. 93 00:06:41,390 --> 00:06:41,840 Right. 94 00:06:42,320 --> 00:06:43,640 It will call on left. 95 00:06:43,640 --> 00:06:45,320 It will get another caller right. 96 00:06:45,320 --> 00:06:47,990 It will get well it is getting mail from the side. 97 00:06:47,990 --> 00:06:49,040 That is case one. 98 00:06:49,550 --> 00:06:50,970 So it will also return. 99 00:06:50,970 --> 00:06:52,970 All right. 100 00:06:53,330 --> 00:06:55,820 So I am returning and returning also for one. 101 00:06:55,820 --> 00:06:59,300 I'm getting mail from both sides, so I will also return. 102 00:06:59,300 --> 00:07:03,410 And now we have this case from the left hand side. 103 00:07:03,410 --> 00:07:06,820 I am getting five from the right hand side, I am getting well. 104 00:07:07,310 --> 00:07:08,600 So this one. 105 00:07:08,600 --> 00:07:09,020 Right. 106 00:07:09,650 --> 00:07:18,050 So in this case, I am returning left, so I will return five and five is the right answer so you can 107 00:07:18,050 --> 00:07:20,150 see how cold is working. 108 00:07:21,020 --> 00:07:26,120 Let's try another call for one more test cases, one more basically three which is given in the indication. 109 00:07:26,420 --> 00:07:31,550 And let's try to understand how our code will work in that case. 110 00:07:35,440 --> 00:07:44,190 Yeah, so let's start the value of B and give this, and this is the root node, so compare three with 111 00:07:44,200 --> 00:07:45,960 five and one, they are different. 112 00:07:45,970 --> 00:07:46,890 I will call on left. 113 00:07:47,260 --> 00:07:49,610 So five and five they are same. 114 00:07:49,630 --> 00:07:51,010 That means the base case. 115 00:07:52,030 --> 00:07:55,060 So my answer will be five and it will return five. 116 00:07:55,330 --> 00:07:57,970 So I will call on this now. 117 00:07:57,970 --> 00:07:58,610 I will check. 118 00:07:59,410 --> 00:08:01,560 So this is one, right? 119 00:08:01,900 --> 00:08:03,130 This is close to this one. 120 00:08:03,340 --> 00:08:04,840 So I will directly return one. 121 00:08:06,970 --> 00:08:14,020 Right, you will like it and do so for three, for three left is not all right, is not an let Miss 122 00:08:14,020 --> 00:08:16,860 Gaisford left exist, right exist. 123 00:08:16,880 --> 00:08:18,900 So in that case, the answer was rude itself. 124 00:08:19,210 --> 00:08:23,480 So my answer is rude itself, which is three and three is direct answer. 125 00:08:24,430 --> 00:08:25,930 So our goal is working. 126 00:08:25,930 --> 00:08:28,310 And now let's discuss their time, complexity. 127 00:08:28,600 --> 00:08:29,650 So what will happen? 128 00:08:29,860 --> 00:08:32,289 You need to go to each and every node. 129 00:08:33,039 --> 00:08:38,200 You will go to each and every time complex it will be, and the total number of nodes that end certain 130 00:08:38,200 --> 00:08:39,970 complexities big off and. 131 00:08:41,789 --> 00:08:42,830 Very simple, right? 132 00:08:44,340 --> 00:08:47,910 And similarly to two lesbians complexity, so if you have Destry. 133 00:08:51,660 --> 00:08:58,050 So if you have this tree, school tree, so what will happen, all the nodes will be present in this 134 00:08:58,470 --> 00:08:59,520 sort of space complex. 135 00:08:59,540 --> 00:09:00,480 It will be big often. 136 00:09:00,490 --> 00:09:03,950 So this is the time and the space complexity for this problem. 137 00:09:04,860 --> 00:09:05,120 Right. 138 00:09:05,490 --> 00:09:07,710 So the code was very, very simple. 139 00:09:08,280 --> 00:09:13,050 But we are doing simple biscuits and other simple, very basic case. 140 00:09:13,440 --> 00:09:16,040 Then you need to search on left and the search and. 141 00:09:16,140 --> 00:09:16,520 Right. 142 00:09:16,530 --> 00:09:24,570 So I'm calling on left and right and then these four cases late, then these four cases and that very 143 00:09:24,570 --> 00:09:27,900 simple recursive algorithm, very simple recursive called. 144 00:09:29,470 --> 00:09:31,370 So this is all over this video, guys. 145 00:09:31,780 --> 00:09:33,340 I will see you in the next one. 146 00:09:33,400 --> 00:09:34,000 Thank you.