1 00:00:00,570 --> 00:00:02,170 Hi, everyone, welcome back. 2 00:00:02,280 --> 00:00:07,740 So in this video, we are going to discuss about a new problem, which is find the lowest common ancestor 3 00:00:07,770 --> 00:00:08,820 of a binary tree. 4 00:00:08,910 --> 00:00:15,610 So we have already solved this problem for binary search tree, but now we have binary tree to the branches 5 00:00:15,630 --> 00:00:20,180 with the same, except that now we have a binary tree and not the best. 6 00:00:20,910 --> 00:00:23,820 So in binary, how we can solve this problem. 7 00:00:23,830 --> 00:00:25,650 So that will be very, very simple. 8 00:00:25,650 --> 00:00:27,870 Using recursion, we can easily solve this problem. 9 00:00:28,470 --> 00:00:30,960 So for example, this is my route node, right? 10 00:00:31,770 --> 00:00:32,790 This is my route node. 11 00:00:32,790 --> 00:00:34,170 So first of all, I will check. 12 00:00:34,380 --> 00:00:39,690 So if P or Q is equal to the root node, then my answer will be node rate. 13 00:00:39,900 --> 00:00:40,770 So very simple. 14 00:00:41,010 --> 00:00:49,720 If your root node is equal to be or your root, nor does it close to Q, then the answer is root and 15 00:00:49,720 --> 00:00:50,470 the answer is root. 16 00:00:50,490 --> 00:00:52,480 So we will return root, right? 17 00:00:52,890 --> 00:00:55,380 So my answer will be root and I will return root. 18 00:00:56,220 --> 00:01:02,890 So now if this is not the case, if Q is not close to root, so what I will do, try to find B income 19 00:01:03,000 --> 00:01:07,080 in the left subtree and try to find being in the right. 20 00:01:07,140 --> 00:01:15,240 Sabry So in case of BSD we can compare root data with the data point and we can decide whether we want 21 00:01:15,240 --> 00:01:17,570 to go left or whether we want to go right. 22 00:01:18,000 --> 00:01:23,510 But since this is a binary so we cannot decide whether we should move left or we should move right, 23 00:01:23,520 --> 00:01:25,340 so we will go in the other direction. 24 00:01:25,350 --> 00:01:32,150 So I will call that equation and I will search B and similarly I will call that goes in the right subtree 25 00:01:32,160 --> 00:01:36,380 and I will try to search B and you know, there are four possibilities. 26 00:01:37,050 --> 00:01:39,390 So let's talk about possibilities. 27 00:01:39,390 --> 00:01:41,100 One, right. 28 00:01:41,280 --> 00:01:42,930 So first, possibility is 29 00:01:45,540 --> 00:01:48,000 being not present in the left subtree. 30 00:01:48,390 --> 00:01:53,880 So it will return B and also not present in the right subtree. 31 00:01:53,880 --> 00:01:54,990 So I will return null. 32 00:01:56,310 --> 00:02:00,630 So being not present, not present in the right subtree. 33 00:02:00,900 --> 00:02:04,950 And also the root data is not close to the data of Bercu. 34 00:02:05,310 --> 00:02:08,400 So B and Q is not present in the. 35 00:02:08,680 --> 00:02:10,050 So my answer will be null. 36 00:02:10,889 --> 00:02:12,000 This is the first case. 37 00:02:12,660 --> 00:02:22,920 Second case can be so in the left subtree being not present I, I'm returning null in the rights of 38 00:02:22,930 --> 00:02:23,640 prepend. 39 00:02:23,640 --> 00:02:27,900 Q is present so I will get some data, I will get basically the root node. 40 00:02:28,260 --> 00:02:34,060 So Birute not Emin's the lowest common ancestor rate. 41 00:02:34,260 --> 00:02:36,420 So FBN good presented the right subtree. 42 00:02:36,420 --> 00:02:40,670 Let's say it is returning the node X X is the lowest common ancestor. 43 00:02:40,860 --> 00:02:46,680 So what I will return, I will return X because X is the answer. 44 00:02:47,460 --> 00:02:50,450 Rate X is a node X is an order. 45 00:02:50,460 --> 00:02:54,360 So I will return the node X and X is the lowest common ancestor. 46 00:02:54,420 --> 00:03:00,500 Fine particles can be the of this one being who is not present in. 47 00:03:00,510 --> 00:03:00,870 Right. 48 00:03:00,870 --> 00:03:04,800 So I will get an L from right and B and you are presently left. 49 00:03:05,100 --> 00:03:08,850 So I will get the answer because it will give me the lowest common ancestor. 50 00:03:09,090 --> 00:03:16,680 So I will get the answer that the lowest common ancestor is Node X, so I will return node X therefore 51 00:03:16,680 --> 00:03:20,370 TKIs fruitcakes can be this is my route. 52 00:03:21,600 --> 00:03:24,900 So one of them is present in the left subtree. 53 00:03:24,900 --> 00:03:32,730 So I will get x rayed that it is the left subtree and similarly I will get some value from the right 54 00:03:32,730 --> 00:03:33,000 supply. 55 00:03:33,120 --> 00:03:39,150 So what I am saying is we can be present in one subtree and gilgan representing another subtree. 56 00:03:39,600 --> 00:03:40,050 Right. 57 00:03:40,590 --> 00:03:42,860 So let's remove actually X and Y. 58 00:03:43,530 --> 00:03:52,410 So here what I want to say for a node, fruit node, what is happening B is present in another subtree 59 00:03:52,410 --> 00:03:55,930 and Q is present in and it is A pre rate or vice versa. 60 00:03:55,950 --> 00:03:58,260 So here we present and Urbis present. 61 00:03:58,620 --> 00:04:00,180 So I will get some value from here. 62 00:04:00,420 --> 00:04:02,420 I will get some value from here. 63 00:04:03,060 --> 00:04:05,190 So in this case, what will be my answer? 64 00:04:05,200 --> 00:04:06,720 What will be the lowest common ancestor? 65 00:04:06,720 --> 00:04:08,850 I think the answer will be root itself. 66 00:04:10,190 --> 00:04:15,980 It so far ruled a. one of the north is lying in the left subtree and another note is lying in another 67 00:04:15,980 --> 00:04:19,610 subtree, so that means the lowest common ancestor is basically the root node. 68 00:04:19,640 --> 00:04:21,950 So I have a little root, right. 69 00:04:22,190 --> 00:04:25,460 So these four are the basic cases that we need to handle. 70 00:04:25,610 --> 00:04:31,560 And if we are able to handle these four cases, then we are done, then we can easily solved discussion. 71 00:04:32,210 --> 00:04:32,610 Right. 72 00:04:33,170 --> 00:04:39,820 So again, first of all, what I will do, I will check this whether the route itself is going to be 73 00:04:39,830 --> 00:04:43,130 OK, if that is the condition, my answer will be ruled itself. 74 00:04:43,370 --> 00:04:49,550 Otherwise, I have these four cases for second, third and fourth cases and I will write the code for 75 00:04:49,550 --> 00:04:56,450 these four cases and that that will be the complete called the coding part of this problem is really, 76 00:04:56,450 --> 00:04:57,200 really simple. 77 00:04:57,620 --> 00:04:59,690 So you can do the coding part yourself. 78 00:04:59,690 --> 00:05:04,220 And in the next redo, if you are not able to do the coding part yourself, then you can always watch 79 00:05:04,220 --> 00:05:05,510 the solution, the next video. 80 00:05:06,470 --> 00:05:09,760 So we will be writing the code together in the next video. 81 00:05:10,100 --> 00:05:11,900 So this is all the supervised. 82 00:05:11,900 --> 00:05:13,430 I will see you in the next one. 83 00:05:13,610 --> 00:05:14,180 Thank you.