1
00:00:00,080 --> 00:00:00,890
Welcome back.

2
00:00:00,890 --> 00:00:07,370
Let's now implement the iterative solution for inorder traversal of the given binary tree okay.

3
00:00:07,370 --> 00:00:13,070
And again as mentioned in the question, as we traverse the binary tree, we will be adding the values

4
00:00:13,070 --> 00:00:15,200
of the nodes to an array.

5
00:00:15,200 --> 00:00:17,030
And then we'll have to finally return it.

6
00:00:17,030 --> 00:00:18,710
So that's given in the question right.

7
00:00:18,710 --> 00:00:20,870
So let's just call this array rest.

8
00:00:20,870 --> 00:00:23,690
And initially this is going to be an empty array.

9
00:00:23,690 --> 00:00:27,500
And finally we will be just returning rest okay.

10
00:00:27,770 --> 00:00:32,450
Now we will also be using a stack as we have discussed in the previous video.

11
00:00:32,450 --> 00:00:35,060
And this is just going to be an empty array initially.

12
00:00:35,060 --> 00:00:41,180
And we will also need a variable, let's call it cur to store the node where we are currently at.

13
00:00:41,180 --> 00:00:43,910
And initially Cur will just be equal to root.

14
00:00:43,910 --> 00:00:49,820
Okay, now we are going to have a while loop, and inside the while loop we will have two conditions.

15
00:00:49,820 --> 00:00:54,590
Either cur should be pointing to a node or the stack should not be empty.

16
00:00:55,040 --> 00:00:58,460
If either of these conditions is true, we will keep looping.

17
00:00:58,460 --> 00:01:01,430
Okay, now inside the while loop.

18
00:01:01,960 --> 00:01:04,960
Will check whether Kerr is pointing to a node.

19
00:01:06,040 --> 00:01:11,710
Because for the inorder traversal, we have to go as much left as possible.

20
00:01:11,710 --> 00:01:16,210
So if Cur is pointing to a valid node, we will just push it to the stack.

21
00:01:16,210 --> 00:01:19,180
So I can say stack dot, push cur.

22
00:01:19,180 --> 00:01:19,690
Okay.

23
00:01:20,050 --> 00:01:22,330
And then I'll just move more to the left.

24
00:01:22,330 --> 00:01:25,900
So I'll say cur is equal to cur dot left.

25
00:01:27,100 --> 00:01:27,670
Okay.

26
00:01:27,670 --> 00:01:33,010
And once we are out of this while loop over here, cur would be not pointing to a node, it would be

27
00:01:33,010 --> 00:01:33,430
null.

28
00:01:33,430 --> 00:01:39,340
And at that point we will say cur is equal to stack dot pop, or we are just popping from the stack

29
00:01:39,340 --> 00:01:40,930
and we are making that cur.

30
00:01:40,960 --> 00:01:41,410
Okay.

31
00:01:41,410 --> 00:01:46,240
And to the results array we will have to at this point push the value of cur.

32
00:01:46,240 --> 00:01:48,250
So rest dot push car dot val.

33
00:01:49,110 --> 00:01:51,210
And then we have to move to the right.

34
00:01:51,210 --> 00:01:53,760
So curve would be equal to curve dot right.

35
00:01:54,420 --> 00:01:54,870
Okay.

36
00:01:54,870 --> 00:01:56,070
And again this is important.

37
00:01:56,070 --> 00:01:59,700
Notice over here we have gone as much left as possible.

38
00:01:59,700 --> 00:02:02,340
And over here we have explored the root node.

39
00:02:02,340 --> 00:02:04,800
And then we have to explore the right node.

40
00:02:04,800 --> 00:02:07,500
So that's the inorder traversal order right.

41
00:02:07,500 --> 00:02:08,460
So that's it.

42
00:02:08,460 --> 00:02:12,540
Now let's go ahead and run this code and see if it's passing all the test cases.

43
00:02:14,190 --> 00:02:15,750
And you can see that it's working.

44
00:02:15,750 --> 00:02:17,460
It's passing all the test cases.

45
00:02:17,460 --> 00:02:24,030
So this is how you can implement the inorder traversal of a given binary tree in an iterative manner.