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.

