1
00:00:00,470 --> 00:00:07,970
So in this question, we are asked to implement in-order traversal for a given binary tree, and we

2
00:00:07,970 --> 00:00:11,210
have to implement the solution in an iterative manner.

3
00:00:11,240 --> 00:00:18,110
Now to start with, let's make a few observations to build the necessary intuition to come up with an

4
00:00:18,110 --> 00:00:19,070
approach for this.

5
00:00:19,100 --> 00:00:26,960
Now, previously when we had discussed inorder traversal in a recursive manner, we had used the recursive

6
00:00:26,960 --> 00:00:27,680
call stack.

7
00:00:27,680 --> 00:00:33,440
But over here, because we are doing it in an iterative manner, we are going to use a stack.

8
00:00:33,440 --> 00:00:33,740
Okay.

9
00:00:33,740 --> 00:00:36,290
So this is going to be the stack that we will be using.

10
00:00:36,290 --> 00:00:41,450
And in the question it's mentioned that we are given the root of the binary tree.

11
00:00:41,450 --> 00:00:45,470
So let's say that we assign the root to a variable called ker.

12
00:00:45,470 --> 00:00:50,900
So ker at this point is pointing to this node over here which is the root node.

13
00:00:50,900 --> 00:00:58,160
Now inorder traversal is about first visiting the left part, then the root and then the right.

14
00:00:58,160 --> 00:00:59,540
So we have seen this previously.

15
00:00:59,540 --> 00:01:02,120
So this is what we mean with inorder traversal.

16
00:01:02,120 --> 00:01:05,900
Now let's continue making a few interesting observations.

17
00:01:05,900 --> 00:01:11,840
So if we were to start over here and again we are given the expected output over here which is the inorder

18
00:01:11,840 --> 00:01:13,370
traversal of this binary tree.

19
00:01:13,370 --> 00:01:14,750
So how do we get this.

20
00:01:14,750 --> 00:01:16,460
So we are starting at the root.

21
00:01:16,460 --> 00:01:18,980
And then we have to go left.

22
00:01:18,980 --> 00:01:20,600
And then we have to again go left.

23
00:01:20,600 --> 00:01:22,970
So because that's what we have over here right.

24
00:01:22,970 --> 00:01:26,600
So when we initially go left we will reach this node over here.

25
00:01:26,600 --> 00:01:28,910
And this becomes the root.

26
00:01:28,910 --> 00:01:35,960
But again at that particular instance we again have to first explore the left before going for the root.

27
00:01:35,960 --> 00:01:38,390
So that's why we'll have to go again left.

28
00:01:38,390 --> 00:01:41,390
And when we reach this node this becomes the root.

29
00:01:41,390 --> 00:01:44,000
And we again have to try to go left.

30
00:01:44,000 --> 00:01:45,260
But there is nothing over here.

31
00:01:45,260 --> 00:01:45,770
Right.

32
00:01:45,770 --> 00:01:50,240
So notice that we have to go left as much as possible.

33
00:01:50,240 --> 00:01:55,130
So this is the first observation that we can make with respect to inorder traversal.

34
00:01:55,130 --> 00:01:59,360
So we need to keep going left as much as possible.

35
00:01:59,360 --> 00:02:03,290
And that's how we get this for over here in the results array.

36
00:02:03,590 --> 00:02:09,320
The second observation that we can make is that once we have added four to the results array.

37
00:02:09,410 --> 00:02:11,750
So we have tried to go left.

38
00:02:11,750 --> 00:02:12,770
There's nothing over here.

39
00:02:12,770 --> 00:02:14,240
Then this is the root.

40
00:02:14,240 --> 00:02:16,010
So we add that over here.

41
00:02:16,010 --> 00:02:17,540
And then we try to go right.

42
00:02:17,540 --> 00:02:18,560
There's nothing over there.

43
00:02:18,560 --> 00:02:25,760
And after that notice that for this subtree we are done exploring the left part.

44
00:02:25,760 --> 00:02:31,070
And we would have to go back to two which at that point becomes the root.

45
00:02:31,070 --> 00:02:34,760
So for this subtree we have explored the left part.

46
00:02:34,760 --> 00:02:39,860
And now we need to add the value two to the results array which is the root.

47
00:02:39,860 --> 00:02:42,860
So this is the second observation that we can make.

48
00:02:42,860 --> 00:02:50,480
Once we are done exploring the left part we need to come back to the previous node, and we have to

49
00:02:50,480 --> 00:02:57,530
do that before we go to the right part, because inorder traversal is all about going left first and

50
00:02:57,530 --> 00:03:02,210
then exploring the root, and after that only going to the right part.

51
00:03:02,210 --> 00:03:04,730
So we have made two interesting observations.

52
00:03:04,730 --> 00:03:10,160
So we have come back over here and we have added the value two also to the results array.

53
00:03:10,160 --> 00:03:12,500
And then we have to go right.

54
00:03:12,500 --> 00:03:12,710
Right.

55
00:03:12,710 --> 00:03:15,530
So that's how the inorder traversal would work.

56
00:03:15,710 --> 00:03:21,650
So we go over here and when we come to five five becomes the root node.

57
00:03:21,650 --> 00:03:29,270
And at this particular instance we have to explore the left part first before we add five to the results

58
00:03:29,270 --> 00:03:29,570
array.

59
00:03:29,570 --> 00:03:34,490
So we'll have to go again left as much as possible which is what we had over here.

60
00:03:34,490 --> 00:03:34,880
Right.

61
00:03:34,880 --> 00:03:37,610
So over here we have to come to the left again.

62
00:03:37,610 --> 00:03:43,250
And when seven becomes the root node we again try to go to the left.

63
00:03:43,250 --> 00:03:46,040
But we are not able to go to the left because there's nothing over here.

64
00:03:46,040 --> 00:03:48,650
And then we add seven to the results array.

65
00:03:48,650 --> 00:03:49,970
So this is how it works.

66
00:03:49,970 --> 00:03:56,510
So the third observation that we can make over here is that after going right, which is what we did

67
00:03:56,510 --> 00:04:00,740
over here, we again need to go left as much as possible.

68
00:04:00,740 --> 00:04:04,430
Again, notice after we went right we again had to keep going left.

69
00:04:04,430 --> 00:04:08,870
Now if we did have more nodes over here, we would have kept going left.

70
00:04:08,870 --> 00:04:12,230
So these are three interesting observations that we have made.

71
00:04:12,230 --> 00:04:20,030
Now let's see how we can use these three observations to come up with the pseudo code for implementing

72
00:04:20,030 --> 00:04:23,240
inorder traversal in an iterative manner.

73
00:04:23,240 --> 00:04:27,560
So the first thing is that we need to keep going left as much as possible.

74
00:04:27,560 --> 00:04:31,580
So again at this point we have cur equal to the root node.

75
00:04:31,580 --> 00:04:35,450
And then we are going to try to keep going left as much as possible.

76
00:04:35,450 --> 00:04:42,860
So while cur points to a node we will append that node to the stack.

77
00:04:42,860 --> 00:04:44,990
And then we will keep going left.

78
00:04:44,990 --> 00:04:49,970
So again at this point we would append one the node one over here to the stack.

79
00:04:49,970 --> 00:04:53,780
And then we'll go to two and we'll append two to the stack.

80
00:04:53,780 --> 00:04:56,840
And then we'll go to four the node with value four.

81
00:04:56,840 --> 00:04:59,600
And then we'll append the node four to the stack.

82
00:04:59,600 --> 00:04:59,930
And.

83
00:05:00,030 --> 00:05:01,770
We will again try to go left.

84
00:05:01,770 --> 00:05:06,750
But at this point, because there's nothing on the left, we would come out of this while loop.

85
00:05:06,750 --> 00:05:13,230
Now, once we are out of the while loop, notice what we did over here was we added this for to the

86
00:05:13,230 --> 00:05:14,040
results array.

87
00:05:14,040 --> 00:05:21,900
So for that we would have to pop from the stack and append the value of the node that we just now popped

88
00:05:21,900 --> 00:05:23,190
to the results array.

89
00:05:23,190 --> 00:05:25,230
So that's how we'll get four over here.

90
00:05:25,230 --> 00:05:31,740
And after we are done with this, we will have to try to go to the right so we can say cur is equal

91
00:05:31,740 --> 00:05:34,260
to the right node of cur.

92
00:05:34,260 --> 00:05:40,710
And this is very important because inorder traversal is all about going first left, then exploring

93
00:05:40,710 --> 00:05:43,140
the root node and then going right.

94
00:05:43,140 --> 00:05:49,050
So we are done exploring the left over here because we went as much as possible to the left.

95
00:05:49,050 --> 00:05:55,140
So we know that at this point where we are at node four, we are not able to go any further left.

96
00:05:55,140 --> 00:05:57,150
So we are done exploring this part.

97
00:05:57,150 --> 00:06:03,600
Then we pop this node over here from the stack and we added the value to the results array.

98
00:06:03,600 --> 00:06:07,950
So over here we are done exploring the root node as well.

99
00:06:07,950 --> 00:06:10,110
And then we have to go to the right.

100
00:06:10,110 --> 00:06:13,770
So that's why we have to say cur is equal to cur dot.

101
00:06:13,770 --> 00:06:14,700
Right okay.

102
00:06:14,700 --> 00:06:18,030
So in this way we will be going to the right node of cur.

103
00:06:18,030 --> 00:06:24,870
And we would have completed exploring the left, the root and the right part for this subtree, if at

104
00:06:24,870 --> 00:06:25,050
all.

105
00:06:25,050 --> 00:06:26,400
There was a subtree over here, right?

106
00:06:26,400 --> 00:06:27,750
Even one node is a subtree.

107
00:06:27,750 --> 00:06:32,970
But again, I'm just saying the case that if we had some nodes over here, we would have to go to this

108
00:06:32,970 --> 00:06:35,430
part before we come back to two.

109
00:06:35,430 --> 00:06:36,720
So that's it.

110
00:06:37,170 --> 00:06:40,110
So at this point this is how our stack looks like.

111
00:06:40,110 --> 00:06:43,380
And we have popped the node four from the stack.

112
00:06:43,380 --> 00:06:45,510
And we have added it to the results array.

113
00:06:45,510 --> 00:06:50,670
Another point to note over here is that we have to keep appending the node.

114
00:06:50,670 --> 00:06:56,460
As we keep going left, we have to keep appending the node to the stack because we need to come back

115
00:06:56,460 --> 00:06:57,240
later.

116
00:06:57,240 --> 00:07:00,780
And before we go right, we have to visit the root node.

117
00:07:00,780 --> 00:07:01,020
Right.

118
00:07:01,020 --> 00:07:05,220
So that's why we have to keep adding the nodes that we visit to the stack.

119
00:07:05,580 --> 00:07:06,180
All right.

120
00:07:06,180 --> 00:07:13,140
Now the last step in the pseudocode for the inorder traversal implemented in an iterative manner would

121
00:07:13,140 --> 00:07:19,680
be to have a while loop over here, and we will keep doing what we discussed over here as long as either

122
00:07:19,680 --> 00:07:21,420
these two conditions is true.

123
00:07:21,420 --> 00:07:24,810
That is, if the stack is not empty, we'll keep doing this.

124
00:07:24,810 --> 00:07:26,820
Or if the cur.

125
00:07:26,850 --> 00:07:32,280
The variable cur is pointing to a node, and if it's not none, we will keep doing this.

126
00:07:32,460 --> 00:07:36,600
Now this is important because let's say we went to the right.

127
00:07:36,600 --> 00:07:41,580
But as we've discussed over here, once we go to the right, we have to keep going left.

128
00:07:41,580 --> 00:07:47,100
Like for example, we came over here and then we have to keep going left as much as possible.

129
00:07:47,100 --> 00:07:48,720
And that would be achieved over here.

130
00:07:48,720 --> 00:07:49,140
Right.

131
00:07:49,140 --> 00:07:51,330
So again we went to the right over here.

132
00:07:51,330 --> 00:07:57,150
And then when we come again to the beginning part of this loop, we would keep going left as much as

133
00:07:57,150 --> 00:07:57,870
possible.

134
00:07:57,870 --> 00:08:03,630
Another reason why we have to keep doing this as long as either of these two conditions is true, is

135
00:08:03,630 --> 00:08:10,080
because we also need to come back and visit the root node, which is what we have done over here.

136
00:08:10,080 --> 00:08:10,230
Right?

137
00:08:10,230 --> 00:08:13,620
So once we're done with this part, we would have to come over here.

138
00:08:13,620 --> 00:08:19,920
So that's why we have to keep doing this because this would be covered by the stack not being empty.

139
00:08:19,920 --> 00:08:25,800
Now we have seen and we have developed a good intuition of how this works.

140
00:08:25,800 --> 00:08:31,740
Now let's solidify our learning by just tracing the algorithm that we've written or the pseudocode that

141
00:08:31,740 --> 00:08:32,700
we have written over here.

142
00:08:32,700 --> 00:08:38,640
So initially Cur is pointing to this node and Cur is not none.

143
00:08:38,640 --> 00:08:40,290
So it's pointing to an actual node.

144
00:08:40,290 --> 00:08:41,460
But the stack is empty.

145
00:08:41,460 --> 00:08:43,020
But this condition is true.

146
00:08:43,020 --> 00:08:44,880
So we enter the while loop.

147
00:08:44,880 --> 00:08:49,200
Now cur is pointing to this node and we will append it to the stack.

148
00:08:49,200 --> 00:08:51,690
So we have the node one in the stack.

149
00:08:51,690 --> 00:08:53,310
And then we go to the left.

150
00:08:53,310 --> 00:08:56,340
So cur is now pointing to this node over here.

151
00:08:56,340 --> 00:08:58,890
And again cur is pointing to a node.

152
00:08:58,890 --> 00:08:59,790
So this is true.

153
00:08:59,790 --> 00:09:02,700
So we again append this node to the stack.

154
00:09:04,700 --> 00:09:06,020
And we go left.

155
00:09:07,400 --> 00:09:10,400
And at this point, again Kurt is pointing to a node.

156
00:09:10,400 --> 00:09:12,830
So we append this node to the stack.

157
00:09:13,980 --> 00:09:15,810
And we try to go left.

158
00:09:15,810 --> 00:09:17,880
And over here there's nothing.

159
00:09:17,880 --> 00:09:19,170
So curb becomes none.

160
00:09:19,170 --> 00:09:22,680
So we come out of this while loop and we come to this part.

161
00:09:22,710 --> 00:09:29,130
Now we are going to pop this and we add the value of this node to the results array.

162
00:09:29,740 --> 00:09:32,530
And then that's this part over here.

163
00:09:32,530 --> 00:09:34,210
And then we are going to go to the right.

164
00:09:34,210 --> 00:09:34,420
Right.

165
00:09:34,420 --> 00:09:38,410
So over here this is cur at this point and we're trying to go to the right.

166
00:09:38,410 --> 00:09:42,040
But again cur is none at this point because there's nothing over here as well.

167
00:09:42,070 --> 00:09:48,460
Now when we come to this condition over here, we see that cur is none, but the stack is not empty,

168
00:09:48,460 --> 00:09:48,940
right?

169
00:09:48,940 --> 00:09:54,040
So it means that there are some nodes whose value has to be yet added to the results array.

170
00:09:54,040 --> 00:09:57,400
So again we come over here and cur is none.

171
00:09:57,400 --> 00:10:00,280
So we come over here and we're going to pop from the stack.

172
00:10:00,280 --> 00:10:03,250
And we'll add the value two to the results array.

173
00:10:03,250 --> 00:10:05,800
And we try to go to the right.

174
00:10:05,800 --> 00:10:07,240
So this was cut at this point.

175
00:10:07,240 --> 00:10:08,530
And we go to the right.

176
00:10:08,530 --> 00:10:11,320
So cur becomes the node five.

177
00:10:11,320 --> 00:10:15,610
And then when we come over here cur is pointing to a node.

178
00:10:15,610 --> 00:10:18,790
And then we come over here and we see that car is not none.

179
00:10:18,790 --> 00:10:22,030
So we append this node over here to the stack.

180
00:10:23,540 --> 00:10:25,430
And we try to go to the left.

181
00:10:25,430 --> 00:10:27,980
And yes, we can because there is a node over here.

182
00:10:27,980 --> 00:10:31,490
So car at this point is pointing to this node over here.

183
00:10:31,490 --> 00:10:34,130
And this is going to be appended to the stack.

184
00:10:34,400 --> 00:10:39,200
And we go left, at which point car becomes none because there's nothing over here.

185
00:10:39,200 --> 00:10:41,270
And we come out of this while loop.

186
00:10:41,270 --> 00:10:48,200
And then over here we are going to pop from the stack and we'll add the value seven to the results array.

187
00:10:48,200 --> 00:10:49,850
And that's over here.

188
00:10:49,850 --> 00:10:51,350
And then we are going to the right.

189
00:10:51,350 --> 00:10:53,150
So again we are trying to go to the right.

190
00:10:53,150 --> 00:10:54,200
But there's nothing over here.

191
00:10:54,200 --> 00:10:55,490
So car becomes none.

192
00:10:55,490 --> 00:10:58,970
So at this point when we come to this condition car is none.

193
00:10:58,970 --> 00:11:00,680
But the stack is not empty.

194
00:11:00,680 --> 00:11:04,550
So again we enter the while loop and car is none.

195
00:11:04,550 --> 00:11:09,530
So we skip this part and we come over here and we are going to pop from the stack.

196
00:11:09,530 --> 00:11:12,080
And we add the value five to the results array.

197
00:11:12,080 --> 00:11:13,910
And we try to move to the right.

198
00:11:13,910 --> 00:11:15,440
And again there's nothing over here.

199
00:11:15,440 --> 00:11:16,700
So car is still none.

200
00:11:16,700 --> 00:11:19,130
And when we come over here car is none.

201
00:11:19,130 --> 00:11:20,660
But the stack is not empty.

202
00:11:20,660 --> 00:11:27,470
So again we enter the loop and we are going to pop from the stack and we add the value one to the results

203
00:11:27,470 --> 00:11:27,890
array.

204
00:11:28,010 --> 00:11:31,070
And then we say that car is car dot right.

205
00:11:31,070 --> 00:11:32,210
So we go to the right.

206
00:11:32,210 --> 00:11:33,560
So we come over here.

207
00:11:33,560 --> 00:11:36,140
Now car is the node with value three.

208
00:11:36,260 --> 00:11:41,990
And then when we come over here we see that car is pointing to a node.

209
00:11:41,990 --> 00:11:45,470
So we append it to the stack and we go left.

210
00:11:45,470 --> 00:11:47,600
So when we go left car becomes none.

211
00:11:47,600 --> 00:11:50,810
And then we come over here we exit this while loop.

212
00:11:50,810 --> 00:11:55,520
We come over here, we're going to pop from the stack, and we'll add the value three to the results

213
00:11:55,520 --> 00:11:55,940
array.

214
00:11:55,940 --> 00:11:58,040
And we try to go to the right.

215
00:11:58,040 --> 00:12:00,050
And yes we have something over here.

216
00:12:00,050 --> 00:12:01,820
So car becomes six.

217
00:12:01,820 --> 00:12:07,850
And then over here we again come to this while loop over here we're going to append six to the stack.

218
00:12:09,250 --> 00:12:12,100
And then over here we are going left.

219
00:12:12,100 --> 00:12:12,820
We'll go left.

220
00:12:12,820 --> 00:12:18,100
So car becomes eight and eight, gets added to the stack and then car becomes none.

221
00:12:18,100 --> 00:12:20,020
So we come out of this while loop.

222
00:12:20,020 --> 00:12:22,960
We pop from the stack which is this eight over here.

223
00:12:22,960 --> 00:12:26,020
And the value eight gets added to the results array.

224
00:12:26,020 --> 00:12:27,790
And we try to go to the right.

225
00:12:27,790 --> 00:12:29,170
But again there's nothing over there.

226
00:12:29,170 --> 00:12:30,880
So car is still none.

227
00:12:30,880 --> 00:12:32,200
And we come over here.

228
00:12:32,200 --> 00:12:32,770
Car is none.

229
00:12:32,770 --> 00:12:34,270
So we come to this part.

230
00:12:34,270 --> 00:12:37,030
We're going to pop from the stack which is this six over here.

231
00:12:37,030 --> 00:12:39,580
And we add the value six to the results array.

232
00:12:39,580 --> 00:12:43,210
At this point car is none and the stack is empty.

233
00:12:43,210 --> 00:12:46,060
So this while loop also is exited.

234
00:12:46,060 --> 00:12:53,230
And notice we were able to traverse the binary tree which was given to us using inorder traversal.

235
00:12:53,230 --> 00:12:56,830
And we implemented this over here in an iterative manner.

236
00:12:59,340 --> 00:13:04,290
In the next video, let's take a look at the space and time complexity of this approach.