1
00:00:01,920 --> 00:00:02,670
Hi, everyone.

2
00:00:02,700 --> 00:00:09,030
So in this video, we are going to solve another question, so we have to construct adultry given the

3
00:00:09,030 --> 00:00:11,440
preorder traversal and reversal of that.

4
00:00:12,330 --> 00:00:17,280
So, for example, this is the product reversal of a tree and this is the reversal of a tree.

5
00:00:17,730 --> 00:00:20,340
And it is obvious that the number of elements will be same.

6
00:00:20,550 --> 00:00:24,390
So given preorder and traversal, we need to construct this tree.

7
00:00:25,280 --> 00:00:30,750
So for distri, this will be my preorder traversal and this will be my traversal.

8
00:00:30,980 --> 00:00:37,010
So basically the input which we are provided is basically the pre order and in order sell and we need

9
00:00:37,010 --> 00:00:39,550
to construct a battery and we need to return the root.

10
00:00:40,620 --> 00:00:45,090
So how we can solve this question, so it's very simple, what is the traversal?

11
00:00:46,320 --> 00:00:53,100
So preordering first day to basically root node, then Brenda left subtree and then print the right

12
00:00:53,100 --> 00:00:53,550
subtree.

13
00:00:54,690 --> 00:01:01,380
And what is the traversal, so in order, first print delectably, then print the road, so then print

14
00:01:01,380 --> 00:01:03,570
the data and then print the right separate.

15
00:01:05,209 --> 00:01:10,940
So first of all, in order to create this tree, I need to identify what is the root, so for finding

16
00:01:10,940 --> 00:01:11,400
out the root.

17
00:01:11,420 --> 00:01:14,030
We know the first element in the traversal is the root.

18
00:01:14,030 --> 00:01:15,110
So tree is the root.

19
00:01:15,560 --> 00:01:16,490
So tree root.

20
00:01:17,580 --> 00:01:22,730
Now, various three percent in the Ed Salvatore's present here, so that means this will be the left

21
00:01:22,770 --> 00:01:26,660
subtree and this is the right side because you can see data.

22
00:01:26,670 --> 00:01:31,030
So before data, we have delectably and after data we have the right subtree.

23
00:01:31,110 --> 00:01:38,450
So that means nine belongs to the left subtree and 15, 20 and seven.

24
00:01:38,460 --> 00:01:40,740
So this belongs to the right subtree.

25
00:01:41,910 --> 00:01:42,320
Simple.

26
00:01:42,660 --> 00:01:43,970
So first step is done.

27
00:01:44,220 --> 00:01:45,070
Now, what will do?

28
00:01:45,080 --> 00:01:48,960
We will collocation on the left subtree and we will collocation on the right subtree.

29
00:01:49,170 --> 00:01:51,680
So far left Sabrin since there is only one node.

30
00:01:51,840 --> 00:01:53,010
So what will be my output.

31
00:01:53,010 --> 00:01:55,500
Simply three and nine because there is only one node.

32
00:01:56,250 --> 00:01:58,110
Now let's discuss for the right subtree.

33
00:01:58,380 --> 00:02:00,200
So 15, 20 and seven.

34
00:02:00,210 --> 00:02:01,620
So this is the right subtree.

35
00:02:01,650 --> 00:02:02,720
15 twenty seven.

36
00:02:03,390 --> 00:02:06,410
And similarly these are the elements 15, 20 and seven.

37
00:02:07,410 --> 00:02:12,720
So this is the broader traversal for the right subtree and this is the in order traversal for the right

38
00:02:12,720 --> 00:02:13,200
subtree.

39
00:02:13,560 --> 00:02:18,500
Now I need to find out the root for the right subtree and various root present.

40
00:02:18,510 --> 00:02:19,550
The first element.

41
00:02:19,770 --> 00:02:21,490
So 20 is the first element.

42
00:02:22,380 --> 00:02:26,610
So 20 now versus 20 present in the traversal.

43
00:02:27,820 --> 00:02:33,700
So 15 will be the last three, because we know when you will print the data in the in order to give

44
00:02:33,700 --> 00:02:37,480
us a left before data, we have left subtree after data we have right.

45
00:02:37,880 --> 00:02:39,910
So 15 is basically the left subtree.

46
00:02:40,180 --> 00:02:41,530
Seven is the right subtree.

47
00:02:41,800 --> 00:02:46,480
So seven is the right subtree since this is a left and right.

48
00:02:46,750 --> 00:02:47,850
But there is only one node.

49
00:02:47,890 --> 00:02:49,300
So this will be my dream.

50
00:02:50,230 --> 00:02:52,410
2010, 15 and then seven.

51
00:02:52,420 --> 00:02:53,470
So you can imagine how.

52
00:02:54,630 --> 00:02:57,400
So that's how you will be able to solve this question.

53
00:02:58,260 --> 00:03:03,090
So what you need to identify, you need to identify what is the right subtree, sorry, what is the

54
00:03:03,090 --> 00:03:06,630
right product reversal and what is the right in order traversal?

55
00:03:06,930 --> 00:03:11,110
Similarly, what is the left preorder traversal and what is left in order traversal?

56
00:03:11,460 --> 00:03:12,720
Let's take one more example.

57
00:03:15,030 --> 00:03:16,150
So this is an example.

58
00:03:16,500 --> 00:03:20,650
So given the traversal and given the traversal, we need to construct a district.

59
00:03:20,940 --> 00:03:23,010
So just remember in the traversal.

60
00:03:23,970 --> 00:03:28,950
So if this is the area of DiPiero Trevathan, first you will print the data.

61
00:03:31,590 --> 00:03:33,600
Then you print the left subtree.

62
00:03:34,880 --> 00:03:36,860
And then you print the right subtree.

63
00:03:39,050 --> 00:03:44,710
And what is in order to save this is the area which is containing the traversal so deeply traversal

64
00:03:44,760 --> 00:03:47,280
area, so these two areas will be of the same size.

65
00:03:47,570 --> 00:03:50,750
So in order traversal first, we print the subtree.

66
00:03:52,100 --> 00:03:56,810
Then we print the root data, then we print the right subtree.

67
00:03:58,250 --> 00:03:59,780
So this is route data.

68
00:04:01,090 --> 00:04:06,760
So let's see how we can solve this question, so first of all, I need to construct this tree and I

69
00:04:06,760 --> 00:04:07,770
need to return the root.

70
00:04:08,380 --> 00:04:09,280
So there is root.

71
00:04:09,280 --> 00:04:11,650
Root is the first element of DiPiero traversal.

72
00:04:11,680 --> 00:04:12,740
So one is the root.

73
00:04:13,210 --> 00:04:14,110
So when is the root?

74
00:04:15,400 --> 00:04:18,160
Now let's find the root in the traversal.

75
00:04:18,160 --> 00:04:23,170
So we will find this data in the traversal so that we can know what is the of and what is the right

76
00:04:23,170 --> 00:04:23,590
subtree.

77
00:04:23,830 --> 00:04:26,170
So we will find one in the traversal.

78
00:04:26,170 --> 00:04:26,850
So this is one.

79
00:04:27,160 --> 00:04:30,850
So that means this is the left subtree and this is the right subtree.

80
00:04:31,660 --> 00:04:41,410
So basically for to belong to left subtree and seven five eight three six belongs to the right subtree.

81
00:04:44,640 --> 00:04:50,860
Simple, so you can see four and two are in delectably and this seven, five, three, six, eight.

82
00:04:50,880 --> 00:04:51,930
This is the subtree.

83
00:04:52,650 --> 00:04:55,190
So now what we will do, we will do exactly the same thing.

84
00:04:55,200 --> 00:04:57,090
So we will call for the left subtree.

85
00:04:57,100 --> 00:04:59,010
We will call the kitchen on the right.

86
00:04:59,400 --> 00:05:02,990
So this tree will be built and it will build this tree.

87
00:05:03,000 --> 00:05:04,280
Also simple.

88
00:05:04,560 --> 00:05:07,980
So for foreign to what we will also for Oriental here.

89
00:05:09,200 --> 00:05:11,570
So this is left in order traversal.

90
00:05:13,280 --> 00:05:19,670
See if you want to build a tree, if you want to build a tree, you need deep water traversal and you

91
00:05:19,670 --> 00:05:20,840
need the traversal.

92
00:05:21,080 --> 00:05:23,300
Now, I want to build the left a tree.

93
00:05:23,700 --> 00:05:25,030
I want to build a tree.

94
00:05:25,040 --> 00:05:30,780
So that means I need left in order traversal and I need left preorder traversal simple.

95
00:05:31,280 --> 00:05:33,890
So what is recursion indication?

96
00:05:34,040 --> 00:05:35,030
What regulation will do?

97
00:05:35,060 --> 00:05:39,550
We will give small, we will give smaller size and same problem.

98
00:05:39,560 --> 00:05:44,340
So the question will solve smaller size problem, but the nature of the problem will be seen.

99
00:05:45,320 --> 00:05:46,390
So what is the big problem?

100
00:05:46,400 --> 00:05:51,470
Big problem is given the bureau traversal of the entire tree, given the diversity of the entire tree

101
00:05:51,470 --> 00:05:53,570
and we need to construct the entire tree.

102
00:05:54,110 --> 00:05:55,570
But here, what is our problem?

103
00:05:56,940 --> 00:06:02,390
We need to build the left subtree only, so we need a left in order to sell and we need left preorder

104
00:06:02,400 --> 00:06:04,150
traversal simple.

105
00:06:04,200 --> 00:06:05,780
So again, the problem is same now.

106
00:06:06,120 --> 00:06:07,800
So this is the first element.

107
00:06:07,800 --> 00:06:08,940
That means this is the root.

108
00:06:09,330 --> 00:06:10,390
Root is the first element.

109
00:06:10,410 --> 00:06:13,500
So that means for the left, Sabry, who is the root?

110
00:06:13,770 --> 00:06:19,870
And so to search two here and four four is basically delectably four will come on the left.

111
00:06:20,220 --> 00:06:21,690
So my left part is complete.

112
00:06:21,840 --> 00:06:23,610
Left is one, two and four.

113
00:06:25,090 --> 00:06:30,850
Now, let's discuss about this, so this is the now I want to build the right subtree, so this is right

114
00:06:30,850 --> 00:06:35,680
in order traversal and this is right preorder traversal.

115
00:06:35,680 --> 00:06:37,660
So this is right preorder traversal.

116
00:06:38,350 --> 00:06:39,930
So we need to construct the route.

117
00:06:40,060 --> 00:06:44,920
What is the route three is the route because in the first element is the route.

118
00:06:45,310 --> 00:06:46,230
So trace route.

119
00:06:46,360 --> 00:06:47,750
So I will search for three here.

120
00:06:47,980 --> 00:06:50,710
So this is the left subtree of three.

121
00:06:50,740 --> 00:06:52,360
This is the right subtree of three.

122
00:06:53,080 --> 00:06:56,590
So I have three here now for the left subtree.

123
00:06:56,590 --> 00:06:58,870
I have seven, five and eight.

124
00:07:00,890 --> 00:07:06,310
This is the left subtree and what is the right subtree of three, right, subtractive six.

125
00:07:06,860 --> 00:07:10,810
You can see this is the three of three and this is the right subtree.

126
00:07:11,540 --> 00:07:15,760
So if there is only one road in the right subtree, we can likely use this three arrows.

127
00:07:16,010 --> 00:07:17,310
So this is complete.

128
00:07:17,750 --> 00:07:22,550
Now we want to discuss how we can build a factory so far building the left subtree.

129
00:07:22,550 --> 00:07:24,450
You need the left to be order traversal.

130
00:07:24,770 --> 00:07:29,970
So this is the left in order traversal and this is the left preorder traversal.

131
00:07:30,980 --> 00:07:33,560
So the first node is basically the root node.

132
00:07:33,740 --> 00:07:35,480
So five is the root node.

133
00:07:35,870 --> 00:07:37,120
So we will search five here.

134
00:07:37,220 --> 00:07:39,420
Seven is in the left, it is in the right.

135
00:07:39,650 --> 00:07:42,620
So seven that left it in the right.

136
00:07:43,550 --> 00:07:46,410
So now my dream is complete and we will attach all the parts.

137
00:07:46,940 --> 00:07:47,970
So what do we have here?

138
00:07:48,530 --> 00:07:49,340
So I have one.

139
00:07:50,930 --> 00:07:54,090
So I have one now, four and two in the left.

140
00:07:54,110 --> 00:07:55,280
So we discussed this is the.

141
00:07:55,610 --> 00:07:56,440
So this is true.

142
00:07:56,450 --> 00:07:59,830
And this is for and we discussed all these elements and.

143
00:07:59,840 --> 00:08:00,140
Right.

144
00:08:00,140 --> 00:08:03,940
So tree is the root, nor is the root, nor in the root of tree.

145
00:08:03,950 --> 00:08:05,840
We have six and four.

146
00:08:05,840 --> 00:08:07,340
These three elements we have discussed.

147
00:08:07,340 --> 00:08:08,040
This is the tree.

148
00:08:08,450 --> 00:08:10,280
So five then seven.

149
00:08:10,280 --> 00:08:10,640
And then.

150
00:08:11,270 --> 00:08:12,410
So now let's match.

151
00:08:14,220 --> 00:08:17,160
So basically, if you will match these two are exactly the same.

152
00:08:19,320 --> 00:08:24,120
So I have one here, one, two and four, then three, five, six, seven, eight, three, five, six,

153
00:08:24,120 --> 00:08:24,860
seven and eight.

154
00:08:25,170 --> 00:08:27,280
So this is how you will be able to solve the problem.

155
00:08:27,600 --> 00:08:28,680
Now let's discuss.

156
00:08:29,830 --> 00:08:31,120
How we can solve this problem.

157
00:08:32,320 --> 00:08:33,090
So basically.

158
00:08:34,409 --> 00:08:35,850
This is in traversal.

159
00:08:37,159 --> 00:08:40,919
And we have traversal, so traversal is Zanardi.

160
00:08:43,070 --> 00:08:44,750
Fyodor Traversal is also an area.

161
00:08:46,460 --> 00:08:55,130
So first, we will bring the left subtree, then we will print the data and then we will print the right

162
00:08:55,130 --> 00:08:55,610
subtree.

163
00:08:56,670 --> 00:09:00,710
And what is the traversal first, you will print that data.

164
00:09:03,090 --> 00:09:07,890
Then you will bring the left subtree and then you will bring the right subtree.

165
00:09:09,240 --> 00:09:10,440
OK, so one question.

166
00:09:11,480 --> 00:09:17,960
So can we build a tree only with the help of another traversal, so, for example, if this is my traversal

167
00:09:18,710 --> 00:09:22,970
120, so what Maitri so I can construct two tree.

168
00:09:23,150 --> 00:09:29,950
So first one is basically like this one, two and three, and the second tree can be one, two and three.

169
00:09:30,260 --> 00:09:32,090
So both the trees are possible.

170
00:09:32,900 --> 00:09:38,630
OK, so if only traversal is given, you can construct the industry and you can also construct of this

171
00:09:38,630 --> 00:09:38,860
tree.

172
00:09:39,140 --> 00:09:44,980
But I want uniquely, I want that my output, my tree should be unique.

173
00:09:44,990 --> 00:09:47,410
So that's why we need Bearder traversal also.

174
00:09:47,630 --> 00:09:55,100
So that's why we need to traversal OK two different Everson's so we can construct tree with the help

175
00:09:55,100 --> 00:09:55,610
of in order.

176
00:09:55,610 --> 00:09:57,170
But that tree will not be unique.

177
00:09:57,680 --> 00:09:59,480
But since I want the unique tree.

178
00:09:59,480 --> 00:10:02,150
So that's why we need the tree also.

179
00:10:03,200 --> 00:10:05,370
So now let's discuss how we can construct that.

180
00:10:05,510 --> 00:10:11,780
So what I will do, I will construct truth, so I will construct the truth and then what I will do.

181
00:10:11,990 --> 00:10:18,030
So I will build the left subtree recursively and I will build the right subtree recursively.

182
00:10:18,650 --> 00:10:19,790
So what is the solution?

183
00:10:20,270 --> 00:10:22,580
I will construct the root node.

184
00:10:23,650 --> 00:10:28,480
I will construct the note not and the coalition will build the left and the right.

185
00:10:29,650 --> 00:10:31,630
OK, so what is the root node?

186
00:10:32,110 --> 00:10:36,310
Root node is basically the first element for constructing the root.

187
00:10:36,580 --> 00:10:37,950
We should note what is the data?

188
00:10:37,960 --> 00:10:43,330
And we know that the data is basically the first element of deputed trevathan so we can easily construct

189
00:10:43,330 --> 00:10:43,840
our own.

190
00:10:44,380 --> 00:10:47,710
Now let's discuss how we can build our left and right subtree.

191
00:10:49,250 --> 00:10:50,870
So what is the problem?

192
00:10:50,900 --> 00:10:58,050
I want to build a tree now for building the tree I need in order traversal and I need to build a traversal.

193
00:10:58,580 --> 00:11:00,950
Now I want to construct the left Sabry.

194
00:11:03,360 --> 00:11:11,460
I want to construct this left subtree, so for constructing this left subtree, I need left in order

195
00:11:11,460 --> 00:11:15,090
traversal and I need left preorder traversal.

196
00:11:15,450 --> 00:11:16,860
So that is the property of recursion.

197
00:11:16,860 --> 00:11:17,160
Right.

198
00:11:17,400 --> 00:11:20,270
So this is the big problem and this is the smaller problem.

199
00:11:20,280 --> 00:11:24,360
So the input size is smaller, but the problem nature is exactly the same.

200
00:11:25,170 --> 00:11:28,230
Now let's see how we can build our lives.

201
00:11:28,240 --> 00:11:29,220
Separate recursively.

202
00:11:30,280 --> 00:11:34,670
So left in order traversal, so for finding the left traversal.

203
00:11:34,690 --> 00:11:40,390
So this is my left in order to listen what I need, I need left in order to start.

204
00:11:41,690 --> 00:11:44,190
And I need left in order.

205
00:11:44,210 --> 00:11:48,890
And so these are indexed left in order to start the next level in order and index.

206
00:11:49,250 --> 00:11:59,510
Similarly, I need left preorder, so I need left preorder starting next and I need left preorder and

207
00:11:59,510 --> 00:11:59,980
index.

208
00:12:00,620 --> 00:12:02,550
So this is what does this.

209
00:12:02,750 --> 00:12:06,000
So this is preorder starting next for the entire day.

210
00:12:06,380 --> 00:12:10,070
This is the preorder and index for the entire trip.

211
00:12:10,400 --> 00:12:13,670
This is the in order starting next for the entire tree.

212
00:12:13,970 --> 00:12:17,070
This is the in order and index for the entire tree.

213
00:12:17,630 --> 00:12:22,970
So if basically, let's say the number of elements are five.

214
00:12:23,480 --> 00:12:24,670
So what is to start?

215
00:12:24,740 --> 00:12:25,330
It is zero.

216
00:12:25,340 --> 00:12:26,000
What is the.

217
00:12:26,370 --> 00:12:30,260
It is basically the first index of the original with the last index of the total number of elements

218
00:12:30,260 --> 00:12:30,650
are five.

219
00:12:30,950 --> 00:12:32,240
So last and next will be four.

220
00:12:32,420 --> 00:12:34,540
So this is your next four and this is your next four.

221
00:12:35,570 --> 00:12:38,660
So I want to left in order that I want left in order.

222
00:12:38,880 --> 00:12:42,350
That means I want to know what is the starting next, what is the ending index?

223
00:12:42,620 --> 00:12:47,450
Similarly for the left preorder area, I need what is the starting next and what is the ending index

224
00:12:47,780 --> 00:12:49,310
and how we can find out this.

225
00:12:49,940 --> 00:12:52,700
So it's very simple what is left in order to start.

226
00:12:52,730 --> 00:12:57,660
So this is the left, so left in order to start this same as in order to start.

227
00:12:57,690 --> 00:13:01,430
So left in order to start is same as the start.

228
00:13:02,970 --> 00:13:09,500
What is left in order and so this is left in order and I don't know what is this index?

229
00:13:09,660 --> 00:13:11,290
So we'll discuss it later.

230
00:13:11,520 --> 00:13:12,920
What is left preorders.

231
00:13:12,930 --> 00:13:13,180
Right.

232
00:13:13,590 --> 00:13:16,350
So this is your start and plus one.

233
00:13:16,470 --> 00:13:17,960
So preorders start.

234
00:13:17,970 --> 00:13:19,250
There's only one element, right?

235
00:13:19,260 --> 00:13:20,210
There's only one element.

236
00:13:20,220 --> 00:13:21,720
So this is the left before the start.

237
00:13:21,990 --> 00:13:25,560
So this is simply preorders start plus one.

238
00:13:25,890 --> 00:13:28,430
Just the next element of the root element.

239
00:13:28,440 --> 00:13:28,920
Simple.

240
00:13:30,330 --> 00:13:34,140
So now let's discuss how we can find out the left in order to end.

241
00:13:34,570 --> 00:13:37,910
OK, so one thing, you know, what is the root element?

242
00:13:38,430 --> 00:13:39,380
You know, the root element.

243
00:13:39,390 --> 00:13:44,920
So you will search this root data in the US and you will light it and then you will search the data.

244
00:13:44,940 --> 00:13:48,480
Let's say the name of this index is root index.

245
00:13:50,050 --> 00:13:51,400
So what is left in order?

246
00:13:51,670 --> 00:13:55,330
So this is the left in order, and that is rootin X minus one.

247
00:13:56,970 --> 00:13:58,800
So this is Rudy Index.

248
00:14:01,870 --> 00:14:03,430
Minus one simple.

249
00:14:04,540 --> 00:14:09,940
This is Rudy, the next you will find out the Rudy next just by iterating over traversal and he will

250
00:14:09,940 --> 00:14:10,290
match the.

251
00:14:11,080 --> 00:14:13,090
So where does my left end?

252
00:14:13,210 --> 00:14:14,840
Just before the Rudy index.

253
00:14:15,070 --> 00:14:16,740
So this is the left hand.

254
00:14:17,200 --> 00:14:20,440
So now let's discuss how we can find out the left preordering.

255
00:14:20,560 --> 00:14:23,370
OK, so one thing, the number of elements will be seen, right?

256
00:14:23,770 --> 00:14:25,540
So a number of elements will be same.

257
00:14:25,570 --> 00:14:26,710
That means left.

258
00:14:27,460 --> 00:14:39,910
So this is left in order and minus left in order to start will be same as left preorder and minus left

259
00:14:40,660 --> 00:14:41,630
preorder start.

260
00:14:41,980 --> 00:14:43,840
So what does this value?

261
00:14:43,840 --> 00:14:52,030
This value is basically the number of elements in the left subtree, number of elements in left subtree.

262
00:14:55,210 --> 00:14:59,230
So a number of elements in the left is going to be same, right?

263
00:14:59,530 --> 00:15:02,180
So this is also the number of elements in the left subtree.

264
00:15:02,300 --> 00:15:03,950
So that's why these two are equals.

265
00:15:04,690 --> 00:15:06,700
So now I know Disvalue.

266
00:15:08,230 --> 00:15:09,310
I know Disvalue.

267
00:15:09,310 --> 00:15:11,680
So I have calculated this value here.

268
00:15:13,420 --> 00:15:15,910
I know Disvalue, so this is the value.

269
00:15:16,910 --> 00:15:21,910
I also know Disvalue, you can see I also know Disvalue, I just need to find out D'Israeli.

270
00:15:22,010 --> 00:15:28,010
So this is an equation which is containing four variables and I know the values of three variables,

271
00:15:28,010 --> 00:15:32,510
disvalue, so disvalue this and this value so we can find out disvalue easily.

272
00:15:32,900 --> 00:15:33,960
And what is this value?

273
00:15:34,280 --> 00:15:35,970
So let's put the value here.

274
00:15:35,990 --> 00:15:39,070
So this is we will take it to the left hand side.

275
00:15:39,680 --> 00:15:44,300
So this is left in order and minus left in order to start.

276
00:15:45,320 --> 00:15:50,250
Plus, left preorder the start, so this is that simple.

277
00:15:51,080 --> 00:15:54,120
So now we will be able to construct our left sabari.

278
00:15:54,190 --> 00:15:57,440
Now we will do exactly the same for the rights of also.

279
00:15:58,760 --> 00:16:01,480
So we need for building the right subtree.

280
00:16:02,270 --> 00:16:03,320
I want to build.

281
00:16:04,490 --> 00:16:06,650
So I want to build the right subtree.

282
00:16:09,480 --> 00:16:17,130
So for building the right subtree, I should know what is the right in order traversal and what is the

283
00:16:17,130 --> 00:16:23,580
right preorder traversal simple so far, right in order traversal.

284
00:16:24,270 --> 00:16:27,270
I need right in order starting next.

285
00:16:28,650 --> 00:16:39,330
And I need right in order and similarly, I need right preorder starting next, I need a right preorder

286
00:16:39,780 --> 00:16:41,300
and indexed simple.

287
00:16:41,610 --> 00:16:43,350
So this is my Doretti.

288
00:16:47,940 --> 00:16:49,950
So first we opened the left subtree.

289
00:16:51,570 --> 00:16:56,460
Then we print the root node and then we print the right subtree.

290
00:16:58,760 --> 00:16:59,870
And what is border?

291
00:17:03,740 --> 00:17:07,550
So for preorder, first we print the root node.

292
00:17:08,730 --> 00:17:16,680
Then we print the left subtree and then we print the right subtree, so let's try to find out these

293
00:17:16,680 --> 00:17:17,369
four values.

294
00:17:17,400 --> 00:17:22,230
So this is in order to start this is in order.

295
00:17:22,240 --> 00:17:24,089
And this is.

296
00:17:25,119 --> 00:17:28,560
Preorder and this is preorder starting next.

297
00:17:30,520 --> 00:17:33,190
So what is right in order starting next?

298
00:17:33,430 --> 00:17:40,720
So in order right, I want to find out this index starting index and we can easily find out this how

299
00:17:41,200 --> 00:17:45,680
you know, the route you will search, you will find out the index.

300
00:17:45,790 --> 00:17:52,120
So I am calling this index is route index and this index is just one next.

301
00:17:52,330 --> 00:17:54,880
So this is route index plus one.

302
00:17:56,180 --> 00:18:03,410
This is Rudy Index plus one, so this is just the next element of the rudiment.

303
00:18:04,920 --> 00:18:10,290
And what is right in order and so right in the end is same as in order.

304
00:18:10,320 --> 00:18:12,700
And so this is the same as in order.

305
00:18:13,680 --> 00:18:16,340
Now let's discuss right from the start.

306
00:18:17,560 --> 00:18:18,000
So.

307
00:18:18,450 --> 00:18:19,100
Right.

308
00:18:19,590 --> 00:18:20,520
So this is right.

309
00:18:20,970 --> 00:18:24,390
And we need to find out this element, the starting element.

310
00:18:25,260 --> 00:18:27,630
So we have already calculated the left.

311
00:18:27,750 --> 00:18:36,210
So if you remember, we have already calculated the left pre order and in just above and we will do

312
00:18:36,210 --> 00:18:36,750
plus one.

313
00:18:37,020 --> 00:18:39,550
So we calculated this value for the left right.

314
00:18:39,570 --> 00:18:46,080
If you remember, we need to do plus one to find out the starting next for the right and what is right

315
00:18:46,080 --> 00:18:46,620
preorder.

316
00:18:46,620 --> 00:18:49,200
And so the same as preordering.

317
00:18:52,410 --> 00:18:59,280
OK, so now we know all that eight values, so you need to find out your values, so for values, for

318
00:18:59,280 --> 00:19:04,950
the right subtree, these four values, and you need to find out these four values.

319
00:19:06,370 --> 00:19:11,290
For the left subtree, for building the left sempre, if you will be able to find out all these values

320
00:19:11,290 --> 00:19:15,720
easily, then you can easily construct your tree and what will be our function.

321
00:19:16,090 --> 00:19:18,570
So our function will take input.

322
00:19:19,330 --> 00:19:28,420
So our function will take as input, preordering ourselves input in order to start in order and preorder,

323
00:19:28,840 --> 00:19:30,600
start pre order.

324
00:19:30,610 --> 00:19:38,110
And so this is how our function will look like, OK, in order to sell the starting next in order and

325
00:19:38,120 --> 00:19:40,720
index preorder starting next, preorder any next.

326
00:19:40,900 --> 00:19:46,650
And we calculated all day values so that we can call on the left Sabry and we can also call them the

327
00:19:46,660 --> 00:19:47,320
right Sabry.

328
00:19:47,830 --> 00:19:50,560
So now I think you will be able to solve this question.

329
00:19:50,830 --> 00:19:53,440
So this question is basically President netcode.

330
00:19:53,650 --> 00:19:59,740
So what I want you guys to do is so first of all try to write the code for this problem yourself and

331
00:19:59,740 --> 00:20:01,510
in the next we do, I will write the code.

332
00:20:02,500 --> 00:20:05,860
So I will discuss the solution, I will write the code in the next renewal.

333
00:20:06,160 --> 00:20:08,160
And first, you should give it a try.

334
00:20:08,500 --> 00:20:10,090
So this is it from this review.

335
00:20:10,090 --> 00:20:11,380
I will see you in the next one.