1
00:00:01,940 --> 00:00:02,700
Hi, everyone.

2
00:00:02,719 --> 00:00:08,300
So in this video, we are going to solve this question, so we need to construct the tree and we are

3
00:00:08,300 --> 00:00:10,760
given the poster traversal and we are given the.

4
00:00:11,900 --> 00:00:14,860
So it is very similar to the last problem that we have solved.

5
00:00:15,110 --> 00:00:17,650
So instead of preorder, we are given post order now.

6
00:00:17,840 --> 00:00:22,700
So, for example, if this is the only or traversal and obviously the number of elements will be the

7
00:00:22,700 --> 00:00:25,930
same in the traversal, so how we can construct that tree.

8
00:00:25,970 --> 00:00:29,230
So first of all, you need to remember what is Deposal Trevathan?

9
00:00:29,390 --> 00:00:37,040
So first we will bring the left sempre, then we bring the right subtree and then we will print the

10
00:00:37,190 --> 00:00:40,020
data and what is in order to listen.

11
00:00:40,340 --> 00:00:46,860
So first we print the left subtree, then we will print the data and then we will print the right.

12
00:00:47,630 --> 00:00:49,060
So this is in order traversal.

13
00:00:49,610 --> 00:00:53,210
So for example, first of all, I need to construct the root node.

14
00:00:53,360 --> 00:00:58,640
So for the node in the portal traversal, the last element is the root node.

15
00:00:58,940 --> 00:01:02,560
So the last element is the root note and now it will do so.

16
00:01:02,570 --> 00:01:06,340
It will search three in two separate left and right separately.

17
00:01:06,830 --> 00:01:11,170
So so each tree he was those three the traversal this is three.

18
00:01:11,330 --> 00:01:14,330
So this is the left subtree and this is the right separate.

19
00:01:14,600 --> 00:01:22,670
So basically nine will be present in the left sempre and 15, 20 and seven is going to be present in

20
00:01:22,670 --> 00:01:23,450
the right subtree.

21
00:01:23,810 --> 00:01:26,630
And now what we will call qualification for the left subtree.

22
00:01:26,630 --> 00:01:30,030
We will qualification for the right subtree since there is only one node.

23
00:01:30,050 --> 00:01:31,730
So this will be only three and nine.

24
00:01:33,170 --> 00:01:40,820
And now let's discuss about 15, 20 and seven, so 15, 20 and seven, so again, so given the big problem,

25
00:01:40,820 --> 00:01:41,720
what is the big problem?

26
00:01:41,720 --> 00:01:47,510
You have to construct that, given the traversal of the entire trillion, given the reversal of the

27
00:01:47,510 --> 00:01:47,900
entire.

28
00:01:48,530 --> 00:01:50,900
So now you want to construct only the right hand side.

29
00:01:51,140 --> 00:01:53,690
You only you only want to construct the right subtree.

30
00:01:53,700 --> 00:01:58,550
So you need the right in order traversal and you need the right traversal.

31
00:01:59,360 --> 00:02:02,140
So the elements are 15, 20 and seven.

32
00:02:02,150 --> 00:02:10,789
So this is the 15, 20 and seven for the right subtree and 15, 27 for the right subtree.

33
00:02:11,270 --> 00:02:15,230
OK, so first of all, we need to construct the root node and root for this present.

34
00:02:15,230 --> 00:02:20,120
At last root is present that lasts for 20 years or so.

35
00:02:20,120 --> 00:02:21,260
20 is the root node.

36
00:02:22,480 --> 00:02:31,960
Now, also not in the traversal, so search, so here is 20 or so, 15 is the left subtree and seven

37
00:02:31,960 --> 00:02:32,860
is the right subtree.

38
00:02:32,860 --> 00:02:34,490
So rude before rude.

39
00:02:34,720 --> 00:02:37,600
We print the subtree, after we print the right.

40
00:02:38,170 --> 00:02:44,260
So that means 15 is going to be present in the left subtree and seven is going to be present in the

41
00:02:44,260 --> 00:02:44,740
right spot.

42
00:02:44,890 --> 00:02:49,650
And since this is only one single node, so twenty, fifteen and seven.

43
00:02:49,900 --> 00:02:53,010
So now the right summary has been constructed that's appended here.

44
00:02:53,290 --> 00:02:57,090
So I have 20, then I have 50 and then I have seven.

45
00:02:57,280 --> 00:02:59,770
So you can match our three Salvatores.

46
00:02:59,770 --> 00:03:00,160
Correct.

47
00:03:01,300 --> 00:03:03,610
So now what we need to do, what is our approach.

48
00:03:03,620 --> 00:03:06,160
So our approach is very simple, what we will do.

49
00:03:06,670 --> 00:03:09,510
So let's write first in order and the posterior traversal.

50
00:03:09,880 --> 00:03:11,050
So in order is.

51
00:03:14,460 --> 00:03:15,270
So this is.

52
00:03:16,360 --> 00:03:23,860
The left first shipment, they left subtree, then reopened the raw data and then we print that out

53
00:03:23,860 --> 00:03:24,340
separately.

54
00:03:27,580 --> 00:03:30,040
And what is the traversal?

55
00:03:34,310 --> 00:03:37,400
First, we print the left subtree.

56
00:03:39,340 --> 00:03:41,440
Then we print the right subtree.

57
00:03:44,340 --> 00:03:47,640
And then we print that so routinely printed at last.

58
00:03:50,500 --> 00:03:56,800
So now our approach is very simple, just exactly like the previous one, so this is your start.

59
00:03:57,580 --> 00:04:00,070
This is the in order and index.

60
00:04:00,520 --> 00:04:03,680
This is post order starting next.

61
00:04:04,330 --> 00:04:09,660
This is post order and index, just like the previous problem.

62
00:04:10,120 --> 00:04:13,090
First of all, we will construct the root node ourself.

63
00:04:13,870 --> 00:04:20,980
Then we will build the left subtree and we will build the right separate using recursion support, constructing

64
00:04:20,980 --> 00:04:21,820
this root node.

65
00:04:22,890 --> 00:04:27,700
We already have the root node, so not only the last element of the potion or traversal.

66
00:04:28,110 --> 00:04:32,130
Now let's see how we can call the equation on the left subtree.

67
00:04:32,580 --> 00:04:38,410
So for building the left subtree, we need left in order traversal and left posterior traversal.

68
00:04:38,910 --> 00:04:48,860
So we need a left in order traversal and we need left posterior traversal for building the left subtree

69
00:04:49,080 --> 00:04:50,150
or left in order.

70
00:04:50,760 --> 00:04:54,630
I need left in order starting next.

71
00:04:55,530 --> 00:05:02,700
I need left in order and indexed similarly for the left posterior traversal.

72
00:05:02,700 --> 00:05:05,310
I need left also starting next.

73
00:05:05,700 --> 00:05:07,380
I need left.

74
00:05:08,480 --> 00:05:10,330
First order and next.

75
00:05:11,410 --> 00:05:18,850
And similarly, if we want to build the right subtree, so for building the right Sabry, we need the

76
00:05:18,850 --> 00:05:26,590
right in order traversal and we need the right most of the traversal for right in order to listen,

77
00:05:26,590 --> 00:05:30,940
I need the right in order starting next.

78
00:05:31,900 --> 00:05:35,230
I need right in order.

79
00:05:35,260 --> 00:05:44,470
And similarly, I need right post order starting next, I need right fast order.

80
00:05:44,590 --> 00:05:49,270
And so again, we need to find out the values for values for left.

81
00:05:50,240 --> 00:05:56,480
For values, for building the left subtree and for values, for building the right subtree, so in total,

82
00:05:56,480 --> 00:05:58,310
we need to find out it values.

83
00:05:59,760 --> 00:06:01,900
So let's see how we can find them.

84
00:06:03,210 --> 00:06:05,430
So let's start with left in order to start.

85
00:06:06,150 --> 00:06:07,260
So this is the left.

86
00:06:08,950 --> 00:06:14,230
And left in order to start this seems in order to start this value was very simple, the same as in

87
00:06:14,230 --> 00:06:14,770
order restaurant.

88
00:06:15,920 --> 00:06:16,750
Left in order.

89
00:06:17,390 --> 00:06:18,650
So right now we don't know.

90
00:06:19,630 --> 00:06:21,440
Left post order start.

91
00:06:22,030 --> 00:06:27,220
So left that start is same as postal start.

92
00:06:27,250 --> 00:06:28,870
So this is same as.

93
00:06:30,590 --> 00:06:36,530
Most order start so left and so right now we don't know this next.

94
00:06:36,680 --> 00:06:38,660
So now let's discuss about right.

95
00:06:38,660 --> 00:06:42,870
In order to start, you need to find out right in order to start.

96
00:06:43,160 --> 00:06:45,120
So right there starts right now.

97
00:06:45,140 --> 00:06:47,480
We don't know this value right in order.

98
00:06:47,480 --> 00:06:50,390
And so right now, we don't know this value.

99
00:06:51,050 --> 00:06:53,150
Right post order start.

100
00:06:53,600 --> 00:06:53,770
So.

101
00:06:53,810 --> 00:06:54,200
Right.

102
00:06:54,200 --> 00:06:56,900
Bulstrode start currently we don't know this value.

103
00:06:57,170 --> 00:06:58,280
Right, Bulstrode?

104
00:06:58,350 --> 00:07:00,410
And we know this value.

105
00:07:00,410 --> 00:07:00,680
Right.

106
00:07:00,710 --> 00:07:01,490
What does this value?

107
00:07:01,670 --> 00:07:01,910
So.

108
00:07:01,910 --> 00:07:03,730
Bulstrode and minus one.

109
00:07:04,190 --> 00:07:05,660
So this value is simple.

110
00:07:05,690 --> 00:07:11,540
This is first order and minus one, the one element before the root element.

111
00:07:12,710 --> 00:07:15,900
So now let's discuss how we can find out this value.

112
00:07:16,730 --> 00:07:18,200
So you know where it is root.

113
00:07:19,400 --> 00:07:25,190
You know, the raw data, so you will search for the raw data in the traversal, you will find out the

114
00:07:25,190 --> 00:07:32,450
raw data and we will call it, we will find out the index and we will call it root index, you know,

115
00:07:32,460 --> 00:07:35,870
root index, what is left in order and so left in order.

116
00:07:35,880 --> 00:07:39,030
And this index just before root index.

117
00:07:39,290 --> 00:07:41,210
So this is root index minus one.

118
00:07:43,000 --> 00:07:50,830
This is rude and X minus one, simple and similarly, what is this index?

119
00:07:50,860 --> 00:07:53,590
So this index is basically right in order to start.

120
00:07:53,650 --> 00:07:55,800
So this is route index plus one.

121
00:07:56,740 --> 00:07:58,540
So we know this is.

122
00:07:59,780 --> 00:08:08,490
Route index plus one, what is right in order and so right in order and is the same as in order.

123
00:08:08,510 --> 00:08:12,710
And so this is same as in order to end.

124
00:08:13,220 --> 00:08:15,740
And now we need to find out only two values.

125
00:08:16,070 --> 00:08:21,290
So we need to find out this value and we need to find out this value, how we can find out this value

126
00:08:21,290 --> 00:08:24,890
exactly like we used to find out in our previous question.

127
00:08:25,140 --> 00:08:28,340
So the number of elements in the left will be seen.

128
00:08:28,340 --> 00:08:32,150
Right number of elements in the poster traversable besame.

129
00:08:32,720 --> 00:08:33,559
So that means.

130
00:08:34,700 --> 00:08:40,700
Left in order and minus left in order to start.

131
00:08:40,940 --> 00:08:49,280
So these are the total number of elements in the traversal will be same as left post or that end minus.

132
00:08:50,380 --> 00:08:52,690
Left for or start.

133
00:08:52,720 --> 00:08:57,580
So these are the total number of elements in the post retriever's and they will be the same number of

134
00:08:57,580 --> 00:08:59,710
elements will be same, you know, disvalue.

135
00:08:59,710 --> 00:09:01,780
You know, this value, you know this value.

136
00:09:01,930 --> 00:09:03,600
You just need to find out this value.

137
00:09:03,760 --> 00:09:05,990
So take it to the left hand side.

138
00:09:06,010 --> 00:09:20,160
So this value will be your left shoulder start, plus left in order and minus left in order to start.

139
00:09:20,710 --> 00:09:22,030
And what is this value?

140
00:09:22,240 --> 00:09:24,410
Right post order start.

141
00:09:24,850 --> 00:09:27,400
So you have calculated this value right now.

142
00:09:28,060 --> 00:09:30,220
OK, you are you have calculated this value.

143
00:09:31,000 --> 00:09:33,840
So this value will be just plus one.

144
00:09:34,390 --> 00:09:42,500
So this will be left for Stalder and plus one left Austro the end plus one.

145
00:09:43,180 --> 00:09:46,590
Now we can construct our tree and how we will call our function.

146
00:09:46,960 --> 00:09:49,320
So we will create a function helper function.

147
00:09:49,720 --> 00:09:53,590
We will pass the traversal, we will pass the total reversal.

148
00:09:53,890 --> 00:09:55,480
We will pass in order to start.

149
00:09:55,780 --> 00:10:01,570
We will pass in order and we will pass also the start and we will pass order end.

150
00:10:02,380 --> 00:10:02,810
Simple.

151
00:10:03,190 --> 00:10:06,060
So this question is also present on later.

152
00:10:06,310 --> 00:10:07,340
So this is the question.

153
00:10:07,780 --> 00:10:09,130
So this is the question.

154
00:10:09,520 --> 00:10:13,220
We have to construct the binary given the in order and the posterior traversal.

155
00:10:13,570 --> 00:10:16,950
So this is exactly similar to the last problem that we have solved.

156
00:10:17,140 --> 00:10:20,930
You can take the help from our last code and you can just modify that code.

157
00:10:21,250 --> 00:10:22,270
So this is it from this?

158
00:10:22,270 --> 00:10:22,660
We do.

159
00:10:22,660 --> 00:10:24,550
In the next we do, we will write the code.

160
00:10:24,820 --> 00:10:28,320
But what I want firstly, you guys should try to implement the code.

161
00:10:28,480 --> 00:10:30,880
It is just the modification of the previous code.

162
00:10:30,910 --> 00:10:34,750
OK, and I have told you how to find out all these eight values.

163
00:10:36,080 --> 00:10:40,670
How to find out all the data values so you can just modify the previous code.

164
00:10:40,880 --> 00:10:44,140
So this is it from this video in the next video we will start implementing.

165
00:10:44,870 --> 00:10:46,400
So I will see you in the next one.

166
00:10:46,470 --> 00:10:46,640
Bye.