1
00:00:01,110 --> 00:00:01,720
Hi, everyone.

2
00:00:01,740 --> 00:00:05,230
So in this video, we are going to discuss what is in seat.

3
00:00:05,640 --> 00:00:07,500
OK, so suppose you have.

4
00:00:08,610 --> 00:00:13,710
This is the root node, you have the left subtree and you have the right subtree.

5
00:00:14,980 --> 00:00:22,810
So in order, Traversal says, first you visit the left subtree, then the data of the root node, so

6
00:00:22,840 --> 00:00:26,840
D stands for the date of the root node and then visit the right subtree.

7
00:00:26,890 --> 00:00:34,540
OK, so in traversal means first left subtree, then the current route node data and then visit the

8
00:00:34,540 --> 00:00:35,240
right separate.

9
00:00:35,320 --> 00:00:38,830
OK, so suppose this is an example of a binary.

10
00:00:39,580 --> 00:00:41,470
So what will be the reversal of this.

11
00:00:42,340 --> 00:00:47,410
So first of all, I have to follow this order left, then data and then the right subtree.

12
00:00:47,740 --> 00:00:50,620
So for one, this entire part is left.

13
00:00:51,580 --> 00:00:56,290
OK, then one will be visited and then the entire right path.

14
00:00:56,290 --> 00:00:58,640
So one will be in the middle.

15
00:00:59,230 --> 00:00:59,920
Now let's see.

16
00:01:00,160 --> 00:01:07,260
So for two, this is the left subtree for so two will be in the middle and four in the left hand side

17
00:01:07,270 --> 00:01:10,210
and five in the right hand side because 550 right separately.

18
00:01:10,240 --> 00:01:13,640
OK, so four one three three right hand side.

19
00:01:13,660 --> 00:01:14,620
So three will come here.

20
00:01:14,650 --> 00:01:18,760
OK, so this will be the inner traversal for this tree.

21
00:01:19,290 --> 00:01:23,540
OK, so you can see clearly for when one is the root node.

22
00:01:23,560 --> 00:01:29,470
So this is the left subtree of one and this is the right subtree of one.

23
00:01:30,360 --> 00:01:34,930
OK, so similarly two is the root node for this Sabry.

24
00:01:36,010 --> 00:01:39,680
For this subtree two is the route also to welcome in the middle.

25
00:01:40,210 --> 00:01:44,680
This is the left subtree for two and this is the right separate photo.

26
00:01:45,740 --> 00:01:48,110
OK, so this is how travel still works.

27
00:01:48,990 --> 00:01:51,580
Now let us perform in our travels along this big tree.

28
00:01:52,360 --> 00:01:54,410
OK, so let's see.

29
00:01:56,690 --> 00:01:59,030
So 25 but I have to perform.

30
00:01:59,030 --> 00:02:00,280
I have to visit left first.

31
00:02:00,290 --> 00:02:02,000
So go to left again.

32
00:02:02,000 --> 00:02:03,140
Go to left again.

33
00:02:03,140 --> 00:02:03,790
Go to left.

34
00:02:03,900 --> 00:02:08,780
So for so first of all, four will come ok then it will go to its parent.

35
00:02:08,780 --> 00:02:11,810
So its parent is ten so I will print ten then.

36
00:02:11,840 --> 00:02:13,400
It's right subtree.

37
00:02:13,430 --> 00:02:17,510
OK, well so this is basically left subtree then.

38
00:02:17,510 --> 00:02:19,030
Data and right subtree.

39
00:02:19,040 --> 00:02:21,060
OK, so for 10 12.

40
00:02:21,080 --> 00:02:24,950
So for chromatin now for 15.

41
00:02:24,950 --> 00:02:26,720
Left subtree has been visited.

42
00:02:26,730 --> 00:02:31,040
So now 15 because they OK and left data.

43
00:02:31,050 --> 00:02:31,440
Right.

44
00:02:32,180 --> 00:02:33,760
So now come to 22.

45
00:02:34,070 --> 00:02:36,410
So for 22 I will visit left subtree.

46
00:02:36,420 --> 00:02:41,870
So it will come first, then 22 and then for 20 to visit the right subtree.

47
00:02:41,870 --> 00:02:42,680
So 24.

48
00:02:43,400 --> 00:02:47,660
OK, so for twenty five then entire life has been visited.

49
00:02:47,660 --> 00:02:49,410
Now visit a. 25.

50
00:02:49,430 --> 00:02:49,940
So right.

51
00:02:49,940 --> 00:02:50,480
25.

52
00:02:51,620 --> 00:02:55,740
Now, since the data has been visited, so I have to visit the right subtree.

53
00:02:56,150 --> 00:02:57,980
OK, now let's visit the right.

54
00:02:58,460 --> 00:03:03,170
OK, so 450 I have to visit the left subtree, left data.

55
00:03:03,200 --> 00:03:03,570
Right.

56
00:03:04,220 --> 00:03:09,170
So it will be 31, then 35.

57
00:03:10,250 --> 00:03:11,470
And then 44.

58
00:03:11,930 --> 00:03:15,440
So 450 has been visited now visit 50.

59
00:03:16,650 --> 00:03:24,780
And now is it the right subtree, so it will be 66, then 70 and then 90, so 66, then 70 and then

60
00:03:24,780 --> 00:03:25,290
90.

61
00:03:26,050 --> 00:03:29,880
OK, so this is the traversal for this mandatory.

62
00:03:31,210 --> 00:03:31,960
OK, symbol.

63
00:03:33,000 --> 00:03:35,760
Now, let us discuss the proposal for this by.

64
00:03:36,240 --> 00:03:41,070
OK, so for one, the left separate does not exist, so left is null.

65
00:03:41,310 --> 00:03:41,730
OK.

66
00:03:43,100 --> 00:03:48,860
Then visit their daughter after visiting the left to visit their data and now visit the right subtree.

67
00:03:49,380 --> 00:03:55,820
OK, so forto I have to visit left first, so I will visit three, then I will visit data, which is

68
00:03:55,820 --> 00:03:59,290
two, and then I will visit the right subtree, which is OK.

69
00:03:59,510 --> 00:04:03,110
So one, three, two is the traversal for this binary.

70
00:04:04,290 --> 00:04:11,280
OK, so I hope you understood the logic first I have to visit left pray for every node, then the data

71
00:04:11,280 --> 00:04:16,000
of the current node and then the right subtree of this node.

72
00:04:16,050 --> 00:04:16,410
OK.

73
00:04:17,670 --> 00:04:23,200
So this left data, right, this is valid for every node.

74
00:04:23,250 --> 00:04:28,500
OK, we have to follow this order for every node, not just for the root node.

75
00:04:28,500 --> 00:04:31,850
We have to follow this order for each and every node in the banditry.

76
00:04:32,220 --> 00:04:34,840
OK, so how are we going to solve this question?

77
00:04:34,890 --> 00:04:35,880
So what will with the code?

78
00:04:35,890 --> 00:04:37,390
So our logic is very simple.

79
00:04:38,370 --> 00:04:40,270
First, I will visit the left.

80
00:04:40,710 --> 00:04:43,350
So first I will visit the left subtree.

81
00:04:43,380 --> 00:04:44,960
So suppose I have a function visit.

82
00:04:45,630 --> 00:04:51,850
So visit function the left subtree, then I have to print the current data.

83
00:04:51,870 --> 00:04:52,620
So which is.

84
00:04:53,830 --> 00:05:00,780
Raw data, and then I have to visit the rights every so often visiting the right subtree, I will call

85
00:05:00,790 --> 00:05:03,550
the function visit and I will give the right subtree.

86
00:05:04,740 --> 00:05:07,050
OK, so we have to write these three lines.

87
00:05:08,340 --> 00:05:11,680
So dysfunction will be a recursive function.

88
00:05:11,700 --> 00:05:17,430
OK, so our goal is going to be recursive, then able to function as basically with it and it is taking

89
00:05:17,430 --> 00:05:18,570
root, not as input.

90
00:05:19,020 --> 00:05:25,680
OK, so we have to follow this order first, visit the laboratory, then visit the data and then visit

91
00:05:25,680 --> 00:05:26,510
the right subtree.

92
00:05:26,820 --> 00:05:27,330
They are.

93
00:05:28,440 --> 00:05:32,910
OK, so since you have understood the logic, now let write the code, OK?

94
00:05:35,150 --> 00:05:41,900
So basically, this question, bindery Binley, they are trying to settle this question, is president

95
00:05:41,900 --> 00:05:42,520
unlettered?

96
00:05:42,530 --> 00:05:46,310
OK, so now let us complete this function, OK?

97
00:05:50,490 --> 00:05:55,320
So you can see here, if the if this is the Binetti, then our output is one to two.

98
00:05:55,430 --> 00:05:59,180
OK, so basically I have two redundant broken pieces we don't have to print.

99
00:05:59,460 --> 00:06:01,590
We have to store it and then we have to get it done.

100
00:06:01,660 --> 00:06:01,980
OK.

101
00:06:04,260 --> 00:06:07,060
So let us first write a simple Internet proposal.

102
00:06:07,150 --> 00:06:09,620
OK, so let's call this function in order.

103
00:06:12,100 --> 00:06:17,410
So suppose it so it takes root, núñez and put.

104
00:06:18,400 --> 00:06:20,150
So first of all, what is the best case?

105
00:06:20,170 --> 00:06:22,780
So basically, it is very simple if rotational.

106
00:06:24,430 --> 00:06:27,320
Then you can simply done there's no need to do anything.

107
00:06:27,340 --> 00:06:30,480
OK, now what do you have to do with the left February first?

108
00:06:30,970 --> 00:06:36,760
So I will call the order function and I will say, hey, visit the left first.

109
00:06:37,870 --> 00:06:42,720
Now, after visiting the left subtree where they will do so, I will visit the current route.

110
00:06:42,730 --> 00:06:43,410
No data.

111
00:06:43,420 --> 00:06:43,660
So.

112
00:06:43,780 --> 00:06:45,370
OK, so rude Altobello.

113
00:06:46,920 --> 00:06:50,610
And after visiting the data, I have to call on the right pretty early.

114
00:06:50,970 --> 00:06:54,180
OK, now we have to call Andy right Subtree.

115
00:06:58,410 --> 00:07:02,180
OK, so this is basically the simple code of ordinary traversal, OK?

116
00:07:03,660 --> 00:07:04,360
Is very simple.

117
00:07:04,800 --> 00:07:08,940
First, I am visiting the subtree, then the data.

118
00:07:11,010 --> 00:07:12,390
And then the right subtree.

119
00:07:15,290 --> 00:07:16,330
OK, simple.

120
00:07:16,850 --> 00:07:22,970
OK, so now let us modified this code for our problem, so I have to return vector of integers, so

121
00:07:22,970 --> 00:07:24,320
let us create a vector.

122
00:07:28,320 --> 00:07:30,240
Veterans to restore our answer.

123
00:07:30,360 --> 00:07:33,530
OK, now let's call this function in order.

124
00:07:34,790 --> 00:07:37,270
OK, so I'm calling the function in order.

125
00:07:39,810 --> 00:07:40,680
I will pass.

126
00:07:40,890 --> 00:07:41,640
They do not.

127
00:07:42,150 --> 00:07:46,200
OK, and I will also have to pass this vector.

128
00:07:46,440 --> 00:07:51,460
OK, distractible, storable, resiled and finally I will return my answer.

129
00:07:51,510 --> 00:07:55,860
OK, I have to return Retrophin pages, so I am returning my answer here.

130
00:07:56,440 --> 00:07:58,980
OK, so let us modify this function.

131
00:07:59,370 --> 00:08:03,260
So it is taking the root node and it is also taking a vector of individuals.

132
00:08:03,300 --> 00:08:03,630
OK.

133
00:08:06,060 --> 00:08:07,830
Let's name a dancer here also.

134
00:08:07,910 --> 00:08:16,520
OK, now, instead of printing the value, what I will do so I will put the value inside the vector.

135
00:08:16,560 --> 00:08:17,860
OK, so answer that.

136
00:08:17,910 --> 00:08:18,540
Push back.

137
00:08:21,800 --> 00:08:24,650
So I'm pushing the value instead of bringing the value.

138
00:08:24,710 --> 00:08:29,440
OK, now one thing, I have to pass this by reference, OK?

139
00:08:30,230 --> 00:08:33,570
I have to pass this vector by defense so that the change is that permanent.

140
00:08:33,620 --> 00:08:37,830
OK, so that here when I'm returning the answer, it is containing the values.

141
00:08:37,850 --> 00:08:40,500
OK, so I have to pass vector by reference, ok.

142
00:08:40,520 --> 00:08:41,390
It is mandatory.

143
00:08:42,470 --> 00:08:43,850
So this is the complete code.

144
00:08:43,880 --> 00:08:45,950
Now letters are now a code and then we will submit.

145
00:08:51,450 --> 00:08:52,890
OK, so there's some mistake.

146
00:08:54,020 --> 00:09:01,760
OK, so we have updated our code, so I have to also pass answer here and similarly, I will pass answer

147
00:09:01,760 --> 00:09:02,030
here.

148
00:09:06,670 --> 00:09:07,870
OK, now let's meet.

149
00:09:14,130 --> 00:09:15,910
OK, so success.

150
00:09:15,930 --> 00:09:17,550
So our goal is working fine.

151
00:09:17,610 --> 00:09:20,850
OK, now let's discuss the time and the space complexity.

152
00:09:23,780 --> 00:09:26,190
OK, so basically, what is the time, complexity?

153
00:09:26,210 --> 00:09:30,890
So what we are doing, we are going through each and every node, so the time complexity is basically

154
00:09:31,250 --> 00:09:34,040
big off and and what is the space complexity?

155
00:09:34,310 --> 00:09:37,010
So space complexity will be all that often OK.

156
00:09:37,040 --> 00:09:38,730
This is due to the concept called stack.

157
00:09:38,810 --> 00:09:41,210
OK, this is called Stack.

158
00:09:42,610 --> 00:09:45,730
So what can happen to our Bindweed can be good to.

159
00:09:45,960 --> 00:09:47,510
OK, so what is as good a tree?

160
00:09:47,830 --> 00:09:51,170
So one, two, three and four.

161
00:09:51,550 --> 00:09:54,130
OK, so this is the example of a school tree.

162
00:09:58,090 --> 00:10:02,130
OK, so what will be the traversal for distri, it will be for three the.

163
00:10:02,680 --> 00:10:05,470
OK, so dedication Kostic what will happen?

164
00:10:06,720 --> 00:10:11,100
So basically, one one will call on two, two will call on three.

165
00:10:11,490 --> 00:10:14,680
Three will call on four and then four will get printed.

166
00:10:14,680 --> 00:10:18,060
Then three will get printed and two will get printed and then one will get printed.

167
00:10:18,090 --> 00:10:19,950
OK, so here they are.

168
00:10:19,950 --> 00:10:20,610
Four node's.

169
00:10:21,730 --> 00:10:26,540
So there are total for in the military and stack sizes basically forward.

170
00:10:26,620 --> 00:10:31,750
OK, so that's why if there are any notes in the worst case, the space complexity will be big often.

171
00:10:31,780 --> 00:10:35,050
OK, in the worst case, space complexity will be big often.

172
00:10:35,290 --> 00:10:36,910
So finally complex.

173
00:10:36,910 --> 00:10:39,910
It is big often because I have to print each and every note.

174
00:10:39,910 --> 00:10:42,820
I am going through each and every node and space complex.

175
00:10:42,820 --> 00:10:48,210
It is big, often in the worst case when the given tree is basically as good a tree.

176
00:10:48,250 --> 00:10:50,410
OK, not a balanced tree.

177
00:10:50,410 --> 00:10:51,420
It is a school tree.

178
00:10:52,210 --> 00:10:53,890
So I hope you understood this question.

179
00:10:53,990 --> 00:10:55,540
OK, thank you.