1
00:00:01,600 --> 00:00:02,260
Hi, everyone.

2
00:00:02,290 --> 00:00:06,250
So in this video, we are going to discuss the preorder, Trevor Salvatore.

3
00:00:06,490 --> 00:00:08,800
OK, so what exactly are the traversal?

4
00:00:09,070 --> 00:00:11,020
So suppose you have a root node.

5
00:00:13,260 --> 00:00:14,550
You have left Sabri.

6
00:00:15,770 --> 00:00:17,180
And you have right subtree.

7
00:00:19,120 --> 00:00:26,200
So preorder traversal CS, first you visit the data, then you go to left and then you go to right.

8
00:00:26,270 --> 00:00:27,560
OK, so what is the.

9
00:00:27,800 --> 00:00:29,590
So this is basically raw data.

10
00:00:29,650 --> 00:00:36,330
OK, so first visit the date of the root node, then visit the left subtree and then visit the right

11
00:00:36,340 --> 00:00:36,780
separately.

12
00:00:36,790 --> 00:00:38,230
OK, so data are left.

13
00:00:38,230 --> 00:00:38,560
Right.

14
00:00:40,090 --> 00:00:46,000
OK, data live right now, let's see this example and let us try to find out the broader traversal for

15
00:00:46,000 --> 00:00:46,490
distri.

16
00:00:46,540 --> 00:00:51,040
OK, so first of all, I'm standing here, so first data.

17
00:00:51,070 --> 00:00:56,210
So one will get printed first, then the left subtree and then the right SIPRI.

18
00:00:56,500 --> 00:00:58,650
OK, so what is the output for everybody?

19
00:00:58,730 --> 00:00:59,650
So first to.

20
00:01:00,690 --> 00:01:07,320
Then they left debris, so for then the right subtree fife, and finally this right subtree three.

21
00:01:07,400 --> 00:01:11,490
OK, so this is the period reversal for this by Nutri.

22
00:01:12,610 --> 00:01:15,250
Now, let us perform the trial set for distri.

23
00:01:15,280 --> 00:01:17,440
OK, so first data.

24
00:01:17,770 --> 00:01:23,290
So one, then the left subtree, so left three does not exist, then the right subtree.

25
00:01:23,320 --> 00:01:27,940
OK, now first two, then the left subtree, which is three.

26
00:01:28,150 --> 00:01:30,910
And then the right subtree, which does not exist.

27
00:01:30,940 --> 00:01:31,390
So it is.

28
00:01:32,470 --> 00:01:35,460
OK, so this is the traversal for this tree.

29
00:01:36,370 --> 00:01:37,510
OK, one, two, three.

30
00:01:38,850 --> 00:01:40,560
Now, let us consider this example.

31
00:01:41,310 --> 00:01:43,000
OK, so first her data.

32
00:01:43,350 --> 00:01:44,640
So that means 25.

33
00:01:46,370 --> 00:01:47,810
Then they left Sabri.

34
00:01:49,750 --> 00:01:57,190
And after left subtree, we have to go for it right subtree, so fallers are pretty a15 so 15 then they

35
00:01:57,190 --> 00:01:59,920
left subtree, so then.

36
00:02:01,020 --> 00:02:07,940
Then they live separately, so for then the right subtree, 12, OK, so 12, 15, then for 12.

37
00:02:09,199 --> 00:02:13,650
Then right subtree, so data left, right.

38
00:02:14,180 --> 00:02:19,580
So it will be 22, 18, 24, then 50.

39
00:02:22,000 --> 00:02:23,200
Then again, 35.

40
00:02:25,150 --> 00:02:30,310
So basically, Rita left and right, so 31 and 44.

41
00:02:32,060 --> 00:02:35,600
So data 70, left, right.

42
00:02:35,810 --> 00:02:37,940
So 66 and 90.

43
00:02:38,180 --> 00:02:41,450
OK, so period reversal is very simple.

44
00:02:41,480 --> 00:02:47,450
First you visit the data, then you visit the left subtree and then you visit the right subtree.

45
00:02:47,480 --> 00:02:50,070
OK, so there is data left, right.

46
00:02:50,300 --> 00:02:53,600
So we have to follow this order for each and every node industry.

47
00:02:53,660 --> 00:02:58,550
OK, we have to follow this order for each and every node of the tree.

48
00:02:59,150 --> 00:03:03,160
OK, so this is the period reversal for this by Nutri.

49
00:03:04,040 --> 00:03:06,060
Now, I hope you understood the question.

50
00:03:06,320 --> 00:03:09,690
So it's called will be very, very simple, but you have to do so.

51
00:03:09,700 --> 00:03:11,090
Suppose you have a function visit.

52
00:03:11,600 --> 00:03:15,210
So what this function will take as input, it will take root as input.

53
00:03:15,770 --> 00:03:16,990
So first of all, data.

54
00:03:17,270 --> 00:03:18,960
So I will print data.

55
00:03:19,010 --> 00:03:20,000
So route data.

56
00:03:21,720 --> 00:03:26,880
Then would I have to do I have to visit the left February, so I will call the function visit and it

57
00:03:26,880 --> 00:03:28,580
will visit the left subtree.

58
00:03:29,680 --> 00:03:31,900
And then I will visit the right subtree.

59
00:03:31,910 --> 00:03:35,970
OK, so I will call the function visit and I will give the right subtree.

60
00:03:37,720 --> 00:03:39,160
OK, very, very simple.

61
00:03:39,310 --> 00:03:41,590
This is data, this is left and this is right.

62
00:03:41,620 --> 00:03:42,490
So data left.

63
00:03:42,490 --> 00:03:42,820
Right.

64
00:03:44,440 --> 00:03:51,500
OK, so since so this is basically a recursive function, OK, the code is very simple.

65
00:03:51,820 --> 00:03:54,790
Now, let us write the code since you have understood the logic.

66
00:03:54,970 --> 00:03:55,330
OK.

67
00:03:56,250 --> 00:04:03,300
So this is the question I have to write the preorder, Trevor said, and the output for this mandatory.

68
00:04:04,370 --> 00:04:09,290
My output is one, two, three, OK, so I have to return vector of integers, I have to Rodenbeck profanity.

69
00:04:09,300 --> 00:04:16,700
Just so first, let us rate what is a simple what is a simple builder driver said, okay, so let's

70
00:04:16,700 --> 00:04:17,959
name dysfunction preordering.

71
00:04:19,430 --> 00:04:20,720
So it will simply take.

72
00:04:22,240 --> 00:04:27,250
No reason, but it will simply take root as input, not a simple case.

73
00:04:27,280 --> 00:04:32,230
So if Rudimental that mystery did not exist, so I can simply return.

74
00:04:33,840 --> 00:04:37,100
OK, I can simply return without printing anything now.

75
00:04:37,180 --> 00:04:39,580
We have to do I have to first print get data.

76
00:04:39,580 --> 00:04:40,140
Left, right.

77
00:04:43,030 --> 00:04:46,740
So data left, right, so this is data then left.

78
00:04:46,930 --> 00:04:49,030
OK, so I will call the function preorder.

79
00:04:50,600 --> 00:04:51,890
And I will pass left.

80
00:04:54,270 --> 00:04:55,290
So after I left.

81
00:04:56,700 --> 00:04:58,320
I have to visit the right subtree.

82
00:05:02,820 --> 00:05:06,660
OK, so I have to follow this order for each and every detail left, right.

83
00:05:09,600 --> 00:05:16,200
OK, so this is very simple code for people traversal, OK, first data, then left and then right.

84
00:05:16,470 --> 00:05:17,290
Data left, right.

85
00:05:17,330 --> 00:05:20,990
OK, now we will modified this code for our question.

86
00:05:21,000 --> 00:05:23,130
OK, so here we do not have to print anything.

87
00:05:23,490 --> 00:05:25,170
We have to return vector of integers.

88
00:05:25,680 --> 00:05:26,880
So let's create.

89
00:05:28,140 --> 00:05:31,890
Avedon said, OK, so let's call it let us call this transfer.

90
00:05:32,700 --> 00:05:34,500
Now I will call the function preorder.

91
00:05:35,610 --> 00:05:43,500
And I will give Root as input and obviously the answer and once I would answer it is ready, I can return

92
00:05:43,500 --> 00:05:43,930
my answer.

93
00:05:43,960 --> 00:05:47,350
OK, I've put a ton of integers, so I'm returning on set here.

94
00:05:48,120 --> 00:05:49,470
Now let us modify this code.

95
00:05:50,160 --> 00:05:56,210
So basically it will take a vector of integer says input and it will fill that vector.

96
00:05:56,220 --> 00:05:58,050
OK, so instead of printing.

97
00:06:00,060 --> 00:06:02,680
I will store the elements, OK?

98
00:06:02,730 --> 00:06:08,220
I have to store instead of printing, so Sadaat pushback value of fruit.

99
00:06:10,120 --> 00:06:14,320
OK, very simple and let us a bit this also so.

100
00:06:17,350 --> 00:06:19,180
Commands and commands.

101
00:06:20,200 --> 00:06:23,120
And one more thing, I have to pass this by reference.

102
00:06:23,140 --> 00:06:28,300
OK, I have to pass it by reference so that the changes are permanent, OK?

103
00:06:29,020 --> 00:06:32,010
Now, let's turn our code and then we will try to submit our code.

104
00:06:32,020 --> 00:06:35,270
OK, now let's submit.

105
00:06:41,680 --> 00:06:42,830
OK, so success.

106
00:06:42,850 --> 00:06:44,350
So our goal is working fine.

107
00:06:44,410 --> 00:06:44,750
OK.

108
00:06:45,100 --> 00:06:49,000
Now let us discuss the time and the space complexity for the preorder reversal.

109
00:06:49,750 --> 00:06:52,470
OK, so consider one example.

110
00:06:52,490 --> 00:06:56,050
So I have one, two and let's say three.

111
00:06:57,620 --> 00:07:03,890
And then let's say for so how the people travel survey work, so I will pass the road and I am passing

112
00:07:04,190 --> 00:07:04,770
the answer.

113
00:07:04,860 --> 00:07:11,200
OK, so initially my answer is somebody then answered or push back rude values or the system.

114
00:07:11,330 --> 00:07:12,650
So I will push one.

115
00:07:13,730 --> 00:07:18,710
Simple, then I'm calling on the left hand side, so left and side is basically nil.

116
00:07:20,220 --> 00:07:25,740
OK, so what is happening here is this is the call stack, so one is calling on the left hand side,

117
00:07:26,430 --> 00:07:27,900
left hand side is basically nil.

118
00:07:28,110 --> 00:07:29,670
OK, so if the route is null, return.

119
00:07:30,030 --> 00:07:31,800
So I will return to one.

120
00:07:32,780 --> 00:07:38,300
OK, then I'm calling on the right hand side, OK, root, right, so I'm calling on the right hand

121
00:07:38,300 --> 00:07:38,540
side.

122
00:07:38,570 --> 00:07:39,890
So when will call to.

123
00:07:40,840 --> 00:07:42,130
One is calling on two.

124
00:07:43,800 --> 00:07:50,790
Then what I will do, so I will push to inside, so we will get inside and then two will call on its

125
00:07:50,790 --> 00:07:54,940
left, so left does not exist for two, so two will call on.

126
00:07:56,130 --> 00:07:57,920
And if the route is well, I will return.

127
00:07:57,930 --> 00:07:59,970
So I will return back to to.

128
00:08:01,010 --> 00:08:03,020
Then will call on the right hand side.

129
00:08:03,180 --> 00:08:05,690
OK, so two will call on three.

130
00:08:07,840 --> 00:08:09,070
Then I will push three.

131
00:08:10,640 --> 00:08:15,260
Then three will call on left, which is for so trivial, calling for.

132
00:08:16,330 --> 00:08:23,530
Then Ford will call in it, so Ford will get inside, then four will call on the left subtree, which

133
00:08:23,530 --> 00:08:23,940
is Nele.

134
00:08:24,220 --> 00:08:30,150
So it will read, I will return to Ford, then Ford will return two, three, three will return to total

135
00:08:30,160 --> 00:08:32,110
return to total return, Duvan.

136
00:08:32,140 --> 00:08:34,240
And finally, of course, tech will become empty.

137
00:08:34,240 --> 00:08:35,190
And this is my answer.

138
00:08:35,200 --> 00:08:36,070
One, two, three, four.

139
00:08:36,100 --> 00:08:39,350
OK, you can see data then left and then right.

140
00:08:40,179 --> 00:08:43,030
So one data left separate does not exist.

141
00:08:43,030 --> 00:08:45,580
Then two data left separate does not exist.

142
00:08:45,850 --> 00:08:51,230
Then three data and then basically four and the right subtree for three did not exist.

143
00:08:51,250 --> 00:08:53,770
So this is how we will get our answer.

144
00:08:53,810 --> 00:09:00,460
OK, and we have to store, OK, we have to pass by reference so that the changes are permanent.

145
00:09:00,640 --> 00:09:06,400
OK, so that time complexity is basically big often because we have to go through each and every node.

146
00:09:06,820 --> 00:09:10,600
OK, and again, the space complexities big off and in the worst case.

147
00:09:10,800 --> 00:09:14,800
OK, so this is same as what in order driver said.

148
00:09:14,830 --> 00:09:16,960
OK, same as traversal.

149
00:09:18,960 --> 00:09:20,190
OK, thank you.

