1
00:00:00,410 --> 00:00:01,490
Welcome back.

2
00:00:01,490 --> 00:00:08,900
Let's now implement the iterative solution for traversing the given binary tree in a post order manner.

3
00:00:08,900 --> 00:00:13,700
And as we have discussed in the previous video, we will be using a stack for this.

4
00:00:13,700 --> 00:00:17,930
And initially we will just fill the root of the given binary tree to the stack.

5
00:00:18,050 --> 00:00:25,280
And we will also be using a visit array to track whether the nodes that have been added to the stack

6
00:00:25,280 --> 00:00:31,010
were added after they were visited, or whether they were added as left and right children.

7
00:00:31,010 --> 00:00:34,160
Okay, and over here we have added the root node.

8
00:00:34,160 --> 00:00:40,430
And in the visit array the first value is going to be false, because at this point the root node has

9
00:00:40,430 --> 00:00:41,420
not been visited.

10
00:00:41,420 --> 00:00:41,810
Okay.

11
00:00:41,810 --> 00:00:48,200
Because if it had been visited, we would have added its left and right children as well to the stack.

12
00:00:48,200 --> 00:00:48,890
Okay.

13
00:00:48,890 --> 00:00:53,480
And we will also need a results array which is initially just empty.

14
00:00:53,480 --> 00:00:58,580
And as we traverse the binary tree we will be adding values to the results array.

15
00:00:58,580 --> 00:01:02,030
And then finally we will be just returning the results array.

16
00:01:02,300 --> 00:01:02,840
Okay.

17
00:01:02,840 --> 00:01:07,280
And as we have discussed in the previous video we are going to have a while loop over here.

18
00:01:07,280 --> 00:01:12,920
And this will keep looping as long as the stack is not empty okay.

19
00:01:12,920 --> 00:01:19,070
And once we are inside the while loop, we are going to pop from the stack and the visit array.

20
00:01:19,070 --> 00:01:29,090
So let me say let car is equal to stack dot pop and let me say let visited is equal to visit dot pop

21
00:01:29,870 --> 00:01:30,380
okay.

22
00:01:30,380 --> 00:01:34,400
And over here we will check whether car is a valid node.

23
00:01:34,400 --> 00:01:39,020
And if that is the case we will check whether visited is true okay.

24
00:01:39,020 --> 00:01:45,470
So if this particular node that we got over here is a node that we did visit, then we would have to

25
00:01:45,470 --> 00:01:48,470
push its value to the results array.

26
00:01:49,670 --> 00:01:50,210
Okay.

27
00:01:50,210 --> 00:01:57,950
But if that is not the case then first we will go ahead and push again this node to the stack.

28
00:01:57,950 --> 00:02:03,470
And at this point in the visit array we will push the value true okay.

29
00:02:03,470 --> 00:02:08,270
Because at this point this node has been added to the stack as a visited node.

30
00:02:08,270 --> 00:02:14,450
Or in other words, we are going to also add its left and right children to the stack over here.

31
00:02:14,450 --> 00:02:17,000
So after this I will say stack, dot, push.

32
00:02:18,070 --> 00:02:19,390
Car dot, right?

33
00:02:20,920 --> 00:02:21,490
Okay.

34
00:02:21,490 --> 00:02:25,600
And in the visit area we will be pushing the value.

35
00:02:25,600 --> 00:02:26,320
False.

36
00:02:26,320 --> 00:02:32,500
Because this node over here has been added to the stack as a right child, not as a root node.

37
00:02:32,500 --> 00:02:32,920
Okay.

38
00:02:32,920 --> 00:02:38,530
Or in other words, the left and right children of this particular node will not be added to the stack

39
00:02:38,530 --> 00:02:39,370
at this point.

40
00:02:39,610 --> 00:02:43,930
Similarly, we will also push the left child to the stack.

41
00:02:43,930 --> 00:02:52,600
So I will say stack dot push car dot left and to the visit array we will push the value false okay.

42
00:02:52,600 --> 00:02:53,530
And that's it.

43
00:02:53,530 --> 00:02:55,030
This should solve the question.

44
00:02:55,030 --> 00:02:59,620
Now let's go ahead and run this code and see if it's passing all the test cases.

45
00:03:00,580 --> 00:03:02,200
And you can see that it's working.

46
00:03:02,200 --> 00:03:03,910
It's passing all the test cases.

47
00:03:03,910 --> 00:03:10,810
So this is how we can implement the postorder traversal of a binary tree in an iterative manner.