1
00:00:01,180 --> 00:00:07,420
Between the in order, post order and preorder iterative functions.

2
00:00:07,420 --> 00:00:11,440
The most difficult one is typically the post order.

3
00:00:11,440 --> 00:00:13,540
And that's what we are trying to do over here.

4
00:00:13,540 --> 00:00:21,550
So first let's start to build the necessary intuition to come up with the solution by making a few interesting

5
00:00:21,550 --> 00:00:22,450
observations.

6
00:00:22,450 --> 00:00:30,940
So as with the preorder and in order iterative solutions over here also we are going to use a stack

7
00:00:30,940 --> 00:00:31,480
okay.

8
00:00:31,480 --> 00:00:34,240
And first let's take an example.

9
00:00:34,420 --> 00:00:39,820
Let's say this is the binary tree which is given to us which is a very simple binary tree.

10
00:00:39,820 --> 00:00:42,490
And we start at the root node.

11
00:00:42,490 --> 00:00:49,780
And in postorder traversal we know that we first go to the left part, then the right part, and finally

12
00:00:49,780 --> 00:00:51,310
process the root node.

13
00:00:51,310 --> 00:00:58,570
So for this simple binary tree over here, the necessary output would be two, three and one because

14
00:00:58,570 --> 00:00:59,650
we first go left.

15
00:00:59,650 --> 00:01:00,850
So we get two over here.

16
00:01:00,850 --> 00:01:02,200
Then we go to the right.

17
00:01:02,200 --> 00:01:03,340
So we get three over here.

18
00:01:03,340 --> 00:01:06,490
And finally we process the root node which is one.

19
00:01:06,490 --> 00:01:10,450
Now how would we get this order from the stack.

20
00:01:10,450 --> 00:01:14,560
Because we know that a stack is a leaf or data structure.

21
00:01:14,560 --> 00:01:16,510
Last in first out.

22
00:01:16,510 --> 00:01:23,950
So we need this two to be the node that enters into the stack as the last node.

23
00:01:24,970 --> 00:01:25,600
Okay.

24
00:01:25,600 --> 00:01:32,080
And the first one to enter the stack has to be this node over here so that we get it out the last.

25
00:01:32,080 --> 00:01:35,500
So this has to be the first one that enters the stack.

26
00:01:35,500 --> 00:01:39,880
So that means that first we'll have to fill one into the stack.

27
00:01:39,880 --> 00:01:44,830
And then three and then two okay.

28
00:01:44,830 --> 00:01:52,150
So to generalize we can say that when we are at a root node first we are going to add the root node

29
00:01:52,150 --> 00:01:53,440
to the stack.

30
00:01:54,080 --> 00:01:59,720
And then we will add the right child to the stack, which is three over here.

31
00:01:59,720 --> 00:02:04,310
And after that we're going to add the left child to the stack.

32
00:02:04,370 --> 00:02:07,280
So this is the first observation that we can make.

33
00:02:07,280 --> 00:02:09,140
So let's note it down.

34
00:02:09,140 --> 00:02:12,140
Add the root node first to the stack.

35
00:02:12,140 --> 00:02:14,420
Then add the right node.

36
00:02:14,420 --> 00:02:16,310
And then add the left node.

37
00:02:16,310 --> 00:02:18,140
And we have seen the reason for this.

38
00:02:18,140 --> 00:02:19,250
In this example.

39
00:02:19,250 --> 00:02:23,930
Let's now continue and make another interesting observation for this.

40
00:02:23,930 --> 00:02:25,580
Let's take another example.

41
00:02:25,580 --> 00:02:28,700
Let's say this is the binary tree which is given to us.

42
00:02:29,030 --> 00:02:34,550
And in this case the expected output would be two, four, three and one.

43
00:02:34,550 --> 00:02:36,320
Because first we go to the left.

44
00:02:36,320 --> 00:02:40,520
And then when we come over here we try to go to the left, but there's nothing over here.

45
00:02:40,520 --> 00:02:41,750
So we go to the right.

46
00:02:41,750 --> 00:02:43,070
So we get four over here.

47
00:02:43,400 --> 00:02:46,340
And then we process the root node which is three.

48
00:02:46,340 --> 00:02:52,880
And finally for this node over here, we are done processing the left part as well as the right part.

49
00:02:52,880 --> 00:02:56,780
And therefore we go ahead and process the root node which is one over here.

50
00:02:56,780 --> 00:03:02,840
So for this binary tree over here the expected output is 243 and one.

51
00:03:02,840 --> 00:03:07,970
Now let's draw our stack over here and make an interesting observation.

52
00:03:07,970 --> 00:03:10,790
So first we start at the root node.

53
00:03:10,790 --> 00:03:15,530
And based on what we have over here we are going to add one to the stack.

54
00:03:15,530 --> 00:03:16,940
And then we'll add three.

55
00:03:16,940 --> 00:03:18,560
And then we will add two okay.

56
00:03:18,560 --> 00:03:21,110
So these three nodes are added to the stack.

57
00:03:21,530 --> 00:03:28,160
Now imagine that we have a while loop that keeps repeating as long as there is something in the stack.

58
00:03:28,160 --> 00:03:31,340
And at this point we see that the stack is not empty.

59
00:03:31,340 --> 00:03:37,370
Now we will see more of this in the latter part of this video, but over here let's just work with this.

60
00:03:37,370 --> 00:03:40,250
So at this point the stack is not empty.

61
00:03:40,250 --> 00:03:47,180
So I pop from the stack and I get two, and I add the value of two to the array over here.

62
00:03:47,180 --> 00:03:49,070
So I have this two over here okay.

63
00:03:49,070 --> 00:03:52,730
Now I continue and I'm going to pop again from the stack.

64
00:03:52,730 --> 00:03:54,410
So I get this three over here.

65
00:03:54,410 --> 00:04:02,390
But notice I cannot add this three to the results array because for the postorder traversal I have to

66
00:04:02,390 --> 00:04:07,460
go first left then right, and then only process the root node.

67
00:04:07,460 --> 00:04:14,000
And over here if I get this three notice that I have not yet processed its left or right children,

68
00:04:14,000 --> 00:04:18,560
so I cannot pop from this and add three to the results array.

69
00:04:18,560 --> 00:04:22,160
Now this is an interesting time to make an observation.

70
00:04:22,160 --> 00:04:30,170
As per what we have discussed so far, a node will get added to the stack in two ways one if it's a

71
00:04:30,170 --> 00:04:30,830
root node.

72
00:04:30,830 --> 00:04:37,070
For example, we added this one over here, which was a root node, or because a node is the left or

73
00:04:37,070 --> 00:04:42,770
right child of a node, for example, two and three were added over here because three is the right

74
00:04:42,770 --> 00:04:44,630
child and two is the left child.

75
00:04:44,630 --> 00:04:49,040
So there are these two ways in which nodes get added to the stack.

76
00:04:49,040 --> 00:04:56,870
Now, if I pop from this stack over here, and if I get a node which was added to the stack when it

77
00:04:56,870 --> 00:05:04,880
was a root node, then I can be sure that its left and right children are already processed.

78
00:05:04,910 --> 00:05:06,290
Now why is that the case?

79
00:05:06,290 --> 00:05:07,520
Because node is over here.

80
00:05:07,520 --> 00:05:09,860
First we add the root node.

81
00:05:10,280 --> 00:05:12,110
Now if I were to draw it in the stack.

82
00:05:12,110 --> 00:05:18,170
So first I add the root node and then it says that we add the right node.

83
00:05:20,560 --> 00:05:22,120
And then we add the left node.

84
00:05:22,120 --> 00:05:22,660
Okay.

85
00:05:24,310 --> 00:05:31,210
So before I get to this node over here, which is a node that was added because it was a root node,

86
00:05:31,210 --> 00:05:39,520
I will have processed already its left and right children, and therefore it follows the Postorder traversal

87
00:05:39,520 --> 00:05:40,150
rule.

88
00:05:40,150 --> 00:05:46,990
And therefore in this case it's okay to add it to the results array, which is something that we did

89
00:05:46,990 --> 00:05:48,400
for two in this case.

90
00:05:48,400 --> 00:05:48,910
Okay.

91
00:05:48,910 --> 00:05:56,650
But if a node was added to the stack because it was the left child or the right child of a particular

92
00:05:56,650 --> 00:06:02,470
node, and let's say I'm popping from the stack, as was the case when I popped from the stack and I

93
00:06:02,470 --> 00:06:09,670
got this node over here, which has the value three, I cannot add it to the results array because I

94
00:06:09,670 --> 00:06:13,840
would not have processed its left or right child.

95
00:06:13,840 --> 00:06:17,500
Okay, so this is an interesting observation to make.

96
00:06:17,500 --> 00:06:23,200
So what we have seen is that there are two possible ways in which nodes can get added to the stack.

97
00:06:23,200 --> 00:06:29,950
The first way is as a root node, and the second way is as a left or right child.

98
00:06:29,950 --> 00:06:37,420
Now if we pop from the stack and if we get a node that was added to the stack as a root node, we are

99
00:06:37,420 --> 00:06:43,930
sure that its left and right children are already processed, and therefore we can go ahead and add

100
00:06:43,930 --> 00:06:45,820
its value to the results array.

101
00:06:45,820 --> 00:06:52,240
But if you are getting a node which was added to the stack because it was a left or right child, then

102
00:06:52,240 --> 00:06:58,750
we cannot add its value to the results array because this particular node's left and right children

103
00:06:58,750 --> 00:07:00,880
are not yet processed.

104
00:07:00,880 --> 00:07:02,860
Okay, so that's what we have seen over here.

105
00:07:02,860 --> 00:07:10,840
And because of this, we will need to be able to differentiate between these two types of nodes that

106
00:07:10,840 --> 00:07:12,670
get added to the stack over here.

107
00:07:12,670 --> 00:07:13,270
Okay.

108
00:07:13,270 --> 00:07:16,720
And for this we will use another stack over here.

109
00:07:16,720 --> 00:07:19,060
Let's just call it visited okay.

110
00:07:19,830 --> 00:07:24,360
Now let's make some space over here and see how this plays out.

111
00:07:24,360 --> 00:07:26,400
So we will use the same example.

112
00:07:26,400 --> 00:07:29,010
So we have this binary tree over here.

113
00:07:29,010 --> 00:07:34,170
And let's say we start with the root node filled in the stack okay.

114
00:07:34,170 --> 00:07:35,820
So we have this node over here.

115
00:07:35,820 --> 00:07:42,930
And then we are going to have a while loop that will keep looping as long as the stack is not empty.

116
00:07:42,930 --> 00:07:48,510
Now at this point we will fill false in the visited stack over here.

117
00:07:48,510 --> 00:07:56,670
Because notice that we just filled the root node to the stack to start with, and we have not yet processed

118
00:07:56,670 --> 00:07:58,530
its left and right children.

119
00:07:58,530 --> 00:08:01,110
Okay, so this is the starting point.

120
00:08:01,110 --> 00:08:07,350
So what you've discussed is we are going to have a while loop that will keep looping as long as the

121
00:08:07,350 --> 00:08:09,600
stack over here is not empty.

122
00:08:09,600 --> 00:08:15,060
And we start with filling the root node to the stack over here and over here.

123
00:08:15,060 --> 00:08:20,880
The value at this point, which corresponds to this node over here, is false, because we have not

124
00:08:20,880 --> 00:08:27,120
processed or we have not added the left and right children of this particular node to the stack over

125
00:08:27,120 --> 00:08:27,510
here.

126
00:08:27,540 --> 00:08:28,980
Now let's get started.

127
00:08:28,980 --> 00:08:37,140
What we are going to do is we are going to pop from the stack and the visited stack from these two inside

128
00:08:37,140 --> 00:08:37,770
the while loop.

129
00:08:37,770 --> 00:08:38,130
Okay.

130
00:08:38,130 --> 00:08:40,560
So I'm going to pop from this and this.

131
00:08:40,560 --> 00:08:44,520
So let me use two variables cur and visit or wish okay.

132
00:08:44,520 --> 00:08:47,550
So Cur is going to equal stack dot pop.

133
00:08:47,550 --> 00:08:50,100
So I get this node to equal to cur.

134
00:08:50,100 --> 00:08:54,360
And this at this point is going to equal false okay.

135
00:08:54,360 --> 00:08:57,240
So cur is one and this is false.

136
00:08:57,570 --> 00:09:01,050
And then I'm going to check if cur is not null.

137
00:09:01,050 --> 00:09:03,780
And if visited is true.

138
00:09:03,960 --> 00:09:10,740
That would mean that this particular node was added to the stack when it was a root node.

139
00:09:10,740 --> 00:09:15,090
Because for only root nodes added to the stack will make visitor true.

140
00:09:15,090 --> 00:09:17,640
So at this point we see that visited is false.

141
00:09:17,640 --> 00:09:19,530
So we come to the else part okay.

142
00:09:19,530 --> 00:09:25,980
So if it was true then we would have added that value to the results array which is what we have discussed

143
00:09:25,980 --> 00:09:27,570
over here okay.

144
00:09:28,170 --> 00:09:34,080
But at this point, because we have false over here, we come to the else part because this at this

145
00:09:34,080 --> 00:09:35,430
point is not truthy.

146
00:09:35,460 --> 00:09:37,200
So we come to the else part.

147
00:09:37,200 --> 00:09:40,290
And over here we are going to do three things.

148
00:09:40,290 --> 00:09:44,190
We are going to append this particular node to the stack.

149
00:09:44,190 --> 00:09:50,580
And at this point we're going to set visited to true because now cur is the root node okay.

150
00:09:50,580 --> 00:09:54,210
So we're going to append this particular node Cur to the stack.

151
00:09:54,210 --> 00:10:00,030
And we're going to append first its right child and then its left child to the stack.

152
00:10:00,030 --> 00:10:01,620
So let's do that over here.

153
00:10:01,620 --> 00:10:06,390
So I can append one and three and two to the stack over here.

154
00:10:06,390 --> 00:10:13,470
Now when we append cur we are going to append true to the visited array, because now cur is a root

155
00:10:13,470 --> 00:10:13,890
node.

156
00:10:13,890 --> 00:10:20,430
And for the right and left children we are going to append false to the visited array because those

157
00:10:20,430 --> 00:10:22,440
two are not root nodes.

158
00:10:22,440 --> 00:10:23,970
Okay, so that's what we have seen.

159
00:10:23,970 --> 00:10:31,230
So whenever a root node is added to the stack will have true which is the case over here.

160
00:10:31,230 --> 00:10:37,890
And for nodes added to the stack because they are either a right child or a left child.

161
00:10:37,890 --> 00:10:44,550
For those scenarios we're going to have false in the visited stack over here because again, we have

162
00:10:44,550 --> 00:10:51,060
seen that for these nodes, we have not yet added their left and right children to the stack.

163
00:10:51,060 --> 00:10:51,630
Okay.

164
00:10:51,630 --> 00:10:52,920
So let's continue.

165
00:10:52,920 --> 00:10:55,770
Now we see that the stack is not empty.

166
00:10:55,770 --> 00:10:57,720
So again we come over here.

167
00:10:57,720 --> 00:11:01,920
We're going to pop from the stack and from the visited stack over here.

168
00:11:01,920 --> 00:11:05,070
And when we do that we get two and false.

169
00:11:05,070 --> 00:11:08,100
So cur is two and at this point is again false.

170
00:11:08,100 --> 00:11:10,770
So we come over here we have a node at cur.

171
00:11:10,770 --> 00:11:12,210
But visited is false.

172
00:11:12,210 --> 00:11:17,400
So we come over here and we're going to append this node to the stack.

173
00:11:18,280 --> 00:11:18,820
Okay.

174
00:11:18,820 --> 00:11:22,060
And we're going to have true in the visited array over here.

175
00:11:22,060 --> 00:11:28,360
And then if it did have right or left children, we would have appended it to the stack.

176
00:11:28,360 --> 00:11:29,470
But it does not have that.

177
00:11:29,470 --> 00:11:29,770
Right.

178
00:11:29,770 --> 00:11:33,250
So two over here as we see does not have any children.

179
00:11:33,250 --> 00:11:37,600
So again we come over here and we see that the stack is not empty.

180
00:11:37,600 --> 00:11:39,610
So we're going to pop from the stack.

181
00:11:39,610 --> 00:11:41,650
And at this point CR is two.

182
00:11:41,650 --> 00:11:44,260
And this is truthy or true okay.

183
00:11:44,260 --> 00:11:52,150
So therefore we come over here and we're going to add the value of this node to the results array which

184
00:11:52,150 --> 00:11:53,650
is what we have over here.

185
00:11:53,920 --> 00:11:57,160
We proceed and we see that the stack is not empty.

186
00:11:57,160 --> 00:12:03,130
So we're again going to pop from the stack and curries three and WIS at this point is false.

187
00:12:03,130 --> 00:12:07,510
And therefore we come over here because this is not truthy.

188
00:12:07,510 --> 00:12:13,810
So we come over here and we're going to append the node with value three to the stack and its right

189
00:12:13,810 --> 00:12:16,180
child, which has a value four to the stack.

190
00:12:16,180 --> 00:12:21,640
Now when we append three over here, the corresponding value is true because this node at this point

191
00:12:21,640 --> 00:12:22,420
is cur right.

192
00:12:22,420 --> 00:12:28,120
So we have seen that for cur, the corresponding value in the visited stack is going to be true, and

193
00:12:28,120 --> 00:12:30,160
for its children it's going to be false.

194
00:12:30,160 --> 00:12:31,840
So that's why we have false over here.

195
00:12:31,840 --> 00:12:36,910
And this is the node with value four which is the right child of this particular node.

196
00:12:36,910 --> 00:12:38,830
Over here again we proceed.

197
00:12:38,830 --> 00:12:41,080
We see that the stack is not empty.

198
00:12:41,080 --> 00:12:45,100
So we're going to pop from the stack and we get four and false.

199
00:12:45,100 --> 00:12:49,240
So again we come to the else part because cur is a node.

200
00:12:49,240 --> 00:12:51,460
But at this point this is false.

201
00:12:51,460 --> 00:12:57,640
So we come to the else part and we're going to append this node to the stack.

202
00:12:57,640 --> 00:13:01,780
And the corresponding value in visited is going to be true okay.

203
00:13:01,780 --> 00:13:04,630
And there are no children for this particular node.

204
00:13:04,630 --> 00:13:05,410
So that's it.

205
00:13:05,410 --> 00:13:09,460
So again we come over here we see that the stack is not empty.

206
00:13:09,460 --> 00:13:13,630
And therefore we come inside this and we're going to pop from the stack.

207
00:13:13,630 --> 00:13:14,470
We get four.

208
00:13:14,470 --> 00:13:16,630
And this at this point is true.

209
00:13:16,630 --> 00:13:18,250
So cur is a node.

210
00:13:18,250 --> 00:13:19,300
And this is true.

211
00:13:19,300 --> 00:13:25,990
So we come over here and we're going to add the value of this particular node which is four to the results

212
00:13:25,990 --> 00:13:27,430
array over here okay.

213
00:13:27,430 --> 00:13:28,600
So we continue.

214
00:13:28,600 --> 00:13:30,010
We again come over here.

215
00:13:30,010 --> 00:13:34,750
We see that the stack is not empty because we have this node over here and this node.

216
00:13:34,750 --> 00:13:36,850
So we're going to pop from the stack.

217
00:13:36,850 --> 00:13:39,160
So cur becomes the node with the value three.

218
00:13:39,160 --> 00:13:41,140
And this is true.

219
00:13:41,140 --> 00:13:42,850
So cur is a valid node.

220
00:13:42,850 --> 00:13:43,930
And this is true.

221
00:13:43,930 --> 00:13:49,780
So we come over here and we are going to append the value of this particular node to the results array

222
00:13:49,780 --> 00:13:51,970
which is this three over here okay.

223
00:13:51,970 --> 00:13:53,200
And we continue.

224
00:13:53,230 --> 00:13:54,730
We again come over here.

225
00:13:54,730 --> 00:13:56,740
We see that the stack is not empty.

226
00:13:56,740 --> 00:13:58,750
So we're going to pop from the stack.

227
00:13:58,750 --> 00:14:01,600
And cur becomes the node with value one.

228
00:14:01,600 --> 00:14:05,200
And this at this point is true because that's what we had over here.

229
00:14:05,200 --> 00:14:07,330
And we see that Cur is a valid node.

230
00:14:07,330 --> 00:14:09,220
And this at this point is true.

231
00:14:09,220 --> 00:14:09,550
Okay.

232
00:14:09,550 --> 00:14:15,550
So we come over here and we're going to append the value of this particular node to the results array

233
00:14:15,550 --> 00:14:17,020
which is this one over here.

234
00:14:17,020 --> 00:14:23,950
So this is how we will be able to traverse the given binary tree in a postorder manner.

235
00:14:23,950 --> 00:14:28,240
And notice that this solution is an iterative solution.