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.

