1
00:00:00,900 --> 00:00:02,340
Hi, everyone, welcome back.

2
00:00:02,370 --> 00:00:07,500
So in this video, we are going to discuss about this question gets my smallest element in about.

3
00:00:08,010 --> 00:00:14,070
So we are provided with the best given about input and our as input.

4
00:00:14,070 --> 00:00:16,149
Right about and have a look.

5
00:00:16,500 --> 00:00:20,090
So we need to find out the key at smallest element in a best.

6
00:00:20,370 --> 00:00:24,420
For example, if the value of KS one, the smallest element will be one.

7
00:00:24,420 --> 00:00:25,530
So my answer should be one.

8
00:00:25,830 --> 00:00:32,369
If the value of KS two, then this element is the second smallest element to my answer should be to.

9
00:00:32,490 --> 00:00:34,080
Let's take one more example.

10
00:00:34,110 --> 00:00:36,190
So let's talk about this one.

11
00:00:36,840 --> 00:00:43,910
So here, if the value of K is, let's say four, I want to find out the fourth smallest element.

12
00:00:44,310 --> 00:00:46,050
So this is the first smallest.

13
00:00:46,380 --> 00:00:47,810
This is the second smallest.

14
00:00:47,850 --> 00:00:49,140
This is the third smallest.

15
00:00:49,140 --> 00:00:51,480
And this is the fourth smallest.

16
00:00:51,480 --> 00:00:54,260
Samantha should be for this node.

17
00:00:54,870 --> 00:00:56,460
So we want to return integer.

18
00:00:56,470 --> 00:00:58,320
So I will not return this compute node.

19
00:00:58,650 --> 00:00:59,430
I will return.

20
00:01:00,330 --> 00:01:01,710
So my answer will be forward.

21
00:01:02,610 --> 00:01:08,580
And if the value of K Street, then this is the third smallest element surmounts I should be three.

22
00:01:08,890 --> 00:01:12,660
So I hope you haven't answered the question that it's very simple.

23
00:01:12,810 --> 00:01:18,900
BSD is provided to us the value of KS provided to us, and we need to find out the smallest element.

24
00:01:18,900 --> 00:01:22,260
And we want to return that element to a very simple solution.

25
00:01:22,260 --> 00:01:22,680
Can be.

26
00:01:23,130 --> 00:01:30,810
We know that if you are provided with the best and if you do in order traversal so traversal of BSG

27
00:01:30,810 --> 00:01:35,600
is basically sorted so we know how to do in traversal.

28
00:01:36,060 --> 00:01:36,690
So what will do?

29
00:01:36,690 --> 00:01:37,910
We will maintain one, Eddie.

30
00:01:39,620 --> 00:01:44,520
They will maintain one at and we will insert all the data in the area.

31
00:01:44,540 --> 00:01:46,270
So I am doing traversal.

32
00:01:46,520 --> 00:01:51,550
So first of all, I am going to visit this node, so I will insert one, then I will visit this.

33
00:01:51,560 --> 00:01:57,740
So I will answer to then I will visit this, I will insert three, then four, then five and then six

34
00:01:57,740 --> 00:01:58,340
and so on.

35
00:01:59,170 --> 00:02:03,770
So basically, when we are doing traversal, we will store the data in this area.

36
00:02:03,820 --> 00:02:05,920
So this area will obviously be assaulted.

37
00:02:06,910 --> 00:02:12,460
So when you're performing in order to store all the data in the area and the area will be a certain

38
00:02:12,460 --> 00:02:12,720
area.

39
00:02:12,850 --> 00:02:15,950
Now, you have a certain area basically, and you have the lucky.

40
00:02:16,450 --> 00:02:21,970
So what you will do, you will simply find out, for example, if the value of case one, they should

41
00:02:21,970 --> 00:02:23,160
be the first value.

42
00:02:24,220 --> 00:02:26,590
So in the area, the indexing starts from zero.

43
00:02:26,640 --> 00:02:32,550
So your answer will be, if this is your area, then your answer will be array of key minus one.

44
00:02:32,860 --> 00:02:35,410
You want to find out the third smallest element.

45
00:02:35,620 --> 00:02:37,180
So add a second index.

46
00:02:37,510 --> 00:02:39,490
The third smallest element is present.

47
00:02:40,000 --> 00:02:43,780
So this will be your answer, three minus one.

48
00:02:44,120 --> 00:02:47,940
So what will be the time and the space complexity of this approach?

49
00:02:48,640 --> 00:02:54,520
So time complexities unit to insert into doing traversal and you will insert all the elements in the

50
00:02:54,520 --> 00:03:00,940
eddy, the time complexities big off and Veronese, the total number of nodes present and similarly

51
00:03:00,940 --> 00:03:02,200
what the be complexity.

52
00:03:02,230 --> 00:03:07,960
So you need to create this area and this area will contain all the nodes of the Chinese history and

53
00:03:08,290 --> 00:03:09,320
the number of nodes that.

54
00:03:09,340 --> 00:03:12,550
And so this is the time and space complexity of this approach.

55
00:03:13,030 --> 00:03:21,790
Now, one more approach can be so you are doing in a reversal rate, you are doing in order traversal.

56
00:03:22,660 --> 00:03:27,020
Let's just maintain one more variable when you are doing in order to that is the variable count.

57
00:03:28,210 --> 00:03:29,790
So what this current variable will do.

58
00:03:30,040 --> 00:03:32,230
So first of all, we are going to visit this node.

59
00:03:32,230 --> 00:03:34,140
So the value of current will become one.

60
00:03:34,540 --> 00:03:36,310
Then we will visit this node.

61
00:03:36,700 --> 00:03:38,470
So the value of count will become two.

62
00:03:38,480 --> 00:03:42,330
I am talking about in order traversal, then I will visit this node.

63
00:03:42,520 --> 00:03:47,380
So the value of current will become three here, here, the value of currently before here, the value

64
00:03:47,380 --> 00:03:48,970
of currently five here.

65
00:03:48,970 --> 00:03:56,020
The value of current will be six and will do so as soon as the value of count become Miklaszewski,

66
00:03:56,560 --> 00:03:57,360
we will stop.

67
00:03:58,720 --> 00:04:04,600
So for example, if the value of Kastari so here the current will become three made what we are doing,

68
00:04:04,600 --> 00:04:07,550
we are simply doing countless plus for every node.

69
00:04:07,780 --> 00:04:09,970
So here I will look.

70
00:04:09,970 --> 00:04:11,520
Initial level of count will be zero.

71
00:04:11,530 --> 00:04:17,040
So I will look Kadal become then I will look on a split second that comes to I will do current plus

72
00:04:17,290 --> 00:04:20,950
the count will become three and three is close to case.

73
00:04:20,950 --> 00:04:22,120
So I will stop here.

74
00:04:22,420 --> 00:04:25,080
I will stop and my answer will be this data.

75
00:04:27,340 --> 00:04:28,190
Simple right.

76
00:04:28,420 --> 00:04:29,430
So what to do.

77
00:04:29,770 --> 00:04:31,570
Just write one helper function.

78
00:04:33,160 --> 00:04:34,150
That helper function.

79
00:04:34,150 --> 00:04:36,620
But it will take, it will take you in order.

80
00:04:37,510 --> 00:04:40,900
It will take the current variable.

81
00:04:40,900 --> 00:04:42,000
And what else?

82
00:04:42,820 --> 00:04:45,520
And it will take your answer.

83
00:04:45,940 --> 00:04:47,770
So in this case, my answer is three.

84
00:04:47,950 --> 00:04:52,390
So when you are stopping what you will do, you will update your answer that your answer is no.

85
00:04:53,650 --> 00:04:54,490
Your answer is No.

86
00:04:54,530 --> 00:04:54,820
Three.

87
00:04:55,120 --> 00:04:57,040
And obviously what will happen.

88
00:04:57,220 --> 00:05:00,110
So this function will call this helper function.

89
00:05:00,130 --> 00:05:07,000
So you need to pass these two variables by reference because I will return the value of answer from

90
00:05:07,000 --> 00:05:07,590
dysfunction.

91
00:05:07,940 --> 00:05:13,930
So I need to pass on several Bio-Reference so that the changes that you are doing here should be reflected

92
00:05:13,930 --> 00:05:15,220
in this main function.

93
00:05:15,370 --> 00:05:20,620
So if you will follow this approach, what they are doing, you are doing in order traversal Magoffin,

94
00:05:20,620 --> 00:05:22,900
but you will not create any extra space.

95
00:05:23,140 --> 00:05:27,310
You will not create any Eddie, since you will use recursion.

96
00:05:27,610 --> 00:05:32,770
And if your tree is like this, that is your tree is as good tree.

97
00:05:34,810 --> 00:05:35,710
So what will happen?

98
00:05:35,900 --> 00:05:39,910
Basically, all these values will be present in this track.

99
00:05:40,450 --> 00:05:44,800
And since all the nodes will be presenting in this taken the worst case.

100
00:05:45,070 --> 00:05:48,340
So time and space complexity still big often and big often.

101
00:05:48,640 --> 00:05:53,860
So we are not improving upon this piece, but we are improving that.

102
00:05:53,860 --> 00:05:59,140
We will not use any we will not use will not need to create another array to solve this problem.

103
00:05:59,140 --> 00:06:02,020
So we are improving space complexity.

104
00:06:02,020 --> 00:06:02,370
Right.

105
00:06:03,850 --> 00:06:09,370
So, yep, you can write the code for the helper function, just perform the.

106
00:06:09,830 --> 00:06:10,970
So this is not in order.

107
00:06:11,020 --> 00:06:16,180
You will take preassembled, it will take three years input and they will perform the write the code

108
00:06:16,180 --> 00:06:25,210
for the traversal and plus if the count becomes equals 2k you know the answer and you will stop.

109
00:06:26,800 --> 00:06:32,620
So the court is going to be very, very simple, in fact, it's so simple that you just need to write

110
00:06:32,620 --> 00:06:36,560
in order traversal court and a little bit of modifications.

111
00:06:37,900 --> 00:06:39,940
So we will be writing the code in the next video.

112
00:06:40,420 --> 00:06:41,620
And I will see you there.

113
00:06:42,940 --> 00:06:43,450
Thank you.