1
00:00:00,110 --> 00:00:00,530
Now.

2
00:00:00,530 --> 00:00:06,620
Previously, we have discussed how we can implement this in a recursive manner, and when we do it in

3
00:00:06,650 --> 00:00:10,490
that way, we are using the recursive call stack.

4
00:00:10,490 --> 00:00:16,700
But over here, because we are trying to implement the iterative solution, we are going to just use

5
00:00:16,700 --> 00:00:18,200
a normal stack for it.

6
00:00:18,740 --> 00:00:19,220
All right.

7
00:00:19,220 --> 00:00:26,240
And again remember we have discussed previously that a stack is a data structure or a last in first

8
00:00:26,240 --> 00:00:27,380
out data structure.

9
00:00:27,380 --> 00:00:32,720
So if you have a stack over here and let's say you add the value one, then you add the value two.

10
00:00:32,720 --> 00:00:39,200
And then if you're trying to remove from the stack, the last value that came into it will be the first

11
00:00:39,200 --> 00:00:40,700
value to come out of it.

12
00:00:40,700 --> 00:00:43,430
So that's why it's last in first out.

13
00:00:43,430 --> 00:00:49,520
And we will use this property of a stack to implement the iterative solution for preorder traversal

14
00:00:49,520 --> 00:00:50,900
of a binary tree.

15
00:00:50,900 --> 00:00:53,240
So let's discuss how we can do this.

16
00:00:53,240 --> 00:00:55,940
So we start with the root node.

17
00:00:55,940 --> 00:00:58,280
And let me add that to a stack.

18
00:00:58,280 --> 00:00:59,720
So I have a stack over here.

19
00:00:59,720 --> 00:01:02,900
And I have added the root node to the stack.

20
00:01:02,900 --> 00:01:07,520
And again remember it's not the value it's the node that I'm adding to the stack.

21
00:01:07,520 --> 00:01:10,430
Now I'm going to have a while loop.

22
00:01:10,430 --> 00:01:15,200
And this is going to repeat as long as something is there in the stack.

23
00:01:15,200 --> 00:01:18,860
And at this point we see that we do have something in the stack.

24
00:01:18,860 --> 00:01:20,960
So we enter the while loop.

25
00:01:20,960 --> 00:01:25,160
So what we'll do over here is first we will pop from the stack.

26
00:01:26,060 --> 00:01:31,880
And then we will add the value of the node that was popped from the stack to an array.

27
00:01:31,880 --> 00:01:33,560
Let's call it the results array.

28
00:01:33,650 --> 00:01:40,220
So if you call this the results array, we're going to add the value of this particular node that was

29
00:01:40,220 --> 00:01:41,720
popped to the results array.

30
00:01:41,720 --> 00:01:46,070
So at this point we are popping this node and it has the value one.

31
00:01:46,070 --> 00:01:48,560
So we add one to the results array.

32
00:01:48,590 --> 00:01:50,510
Again I'm just showing it over here.

33
00:01:50,510 --> 00:01:52,400
Initially the results array is empty.

34
00:01:52,400 --> 00:01:55,310
And at this point it will just have the value one.

35
00:01:55,340 --> 00:02:02,090
Now we will first add the right child of this particular node to the stack.

36
00:02:02,090 --> 00:02:05,210
And again it's of course only if it does have a right child.

37
00:02:05,210 --> 00:02:10,370
And then we will add the left child of the particular node to the stack.

38
00:02:10,400 --> 00:02:17,060
Now this order is important because for the preorder traversal we have root.

39
00:02:17,060 --> 00:02:18,380
And then we have left.

40
00:02:18,380 --> 00:02:19,670
And then we have right.

41
00:02:19,670 --> 00:02:24,830
So we have to visit the left node before visiting the right node.

42
00:02:24,830 --> 00:02:30,320
And we are adding the right child first before adding the left child.

43
00:02:30,320 --> 00:02:36,530
Because let's say I've added the right child that's at this point over here.

44
00:02:36,530 --> 00:02:38,840
And then I am adding the left child.

45
00:02:40,430 --> 00:02:44,330
Now because a stack is a data structure.

46
00:02:44,330 --> 00:02:48,230
When I pop from this, I'm going to get left before right?

47
00:02:48,230 --> 00:02:51,620
And that is something which is important for preorder traversal.

48
00:02:51,620 --> 00:02:54,980
So I have to get the left node before the right node.

49
00:02:54,980 --> 00:02:58,400
And that's why we will add the right node first.

50
00:02:59,240 --> 00:03:01,760
And then we will add the left node.

51
00:03:01,760 --> 00:03:07,400
And this is of course only if the node at hand does have a right and left child.

52
00:03:07,400 --> 00:03:09,590
So this is how we're going to approach this.

53
00:03:09,590 --> 00:03:10,580
So let's see.

54
00:03:10,580 --> 00:03:13,940
And just let's trace the algorithm and see what's going to happen.

55
00:03:13,940 --> 00:03:16,190
So at this point we have node one.

56
00:03:16,190 --> 00:03:20,450
And you can see that it does have a left child and a right child.

57
00:03:20,450 --> 00:03:25,130
So first I'm going to add the right child which has the value three.

58
00:03:25,130 --> 00:03:28,520
So the node three is going to get added to the stack.

59
00:03:28,520 --> 00:03:34,400
And then the left child which is this node over here which is two will be added to the stack.

60
00:03:34,400 --> 00:03:41,600
And again all of these are nodes because later once we pop this we'll need to check whether that particular

61
00:03:41,600 --> 00:03:43,430
node has a left or right child.

62
00:03:43,430 --> 00:03:47,600
And if we were to just add values to the stack, we would not be able to do that.

63
00:03:47,600 --> 00:03:50,840
So that's why we have to keep adding nodes to the stack.

64
00:03:50,990 --> 00:03:51,590
All right.

65
00:03:51,590 --> 00:03:54,200
So we have two and three in the stack.

66
00:03:54,200 --> 00:03:56,960
And then we see that the stack is not empty.

67
00:03:56,960 --> 00:04:01,190
So therefore we come over here and we are going to pop from the stack.

68
00:04:01,190 --> 00:04:05,990
And again we're going to pop from the top because a stack is a data structure.

69
00:04:05,990 --> 00:04:12,860
So we pop the node two and we're going to add the value of this particular node which is two to the

70
00:04:12,860 --> 00:04:13,760
results array.

71
00:04:13,910 --> 00:04:18,230
And then we're going to check whether this node has a right child.

72
00:04:18,230 --> 00:04:20,480
And we can see that it does have a right child.

73
00:04:20,480 --> 00:04:23,270
So we're going to add this node to the stack.

74
00:04:23,270 --> 00:04:24,890
So we have five added over here.

75
00:04:24,980 --> 00:04:28,220
And then we also add the left child which is four.

76
00:04:28,220 --> 00:04:30,170
So we have four and five over here.

77
00:04:30,170 --> 00:04:32,150
And the stack is not empty.

78
00:04:32,150 --> 00:04:37,190
So we pop from the stack and we add the value of four to the results array.

79
00:04:37,310 --> 00:04:42,890
And we see that this particular node does not have a left or right child.

80
00:04:42,890 --> 00:04:44,090
So we proceed.

81
00:04:44,090 --> 00:04:47,000
And at this point again the stack is not empty.

82
00:04:47,000 --> 00:04:50,210
So we come over here and we're going to pop from the stack.

83
00:04:50,210 --> 00:04:52,850
And we'll add the value five to the results array.

84
00:04:53,000 --> 00:04:56,510
And this node over here does have a left child.

85
00:04:56,510 --> 00:04:59,120
So we're going to add that child over here.

86
00:04:59,120 --> 00:05:01,070
Again notice it does not have a right child.

87
00:05:01,070 --> 00:05:04,370
So we can't add anything for this line of code.

88
00:05:04,370 --> 00:05:07,400
But over here we see that it does have a left child.

89
00:05:07,400 --> 00:05:10,640
So we add the node seven to the stack.

90
00:05:12,030 --> 00:05:13,290
And then we come again.

91
00:05:13,290 --> 00:05:16,350
Over here, we see that the stack is not empty.

92
00:05:16,920 --> 00:05:22,290
Therefore, we are going to pop from the stack and we'll add the value to the results array.

93
00:05:22,290 --> 00:05:26,430
And this node over here does not have a left or right child.

94
00:05:26,430 --> 00:05:28,830
So nothing gets added to the stack.

95
00:05:28,830 --> 00:05:31,080
And we again come over here.

96
00:05:31,080 --> 00:05:32,340
The stack is not empty.

97
00:05:32,340 --> 00:05:36,120
So we pop from the stack and we add the value to the results array.

98
00:05:36,300 --> 00:05:41,310
And at this point we check whether this node has a right child.

99
00:05:41,310 --> 00:05:42,960
It does have a right child.

100
00:05:42,960 --> 00:05:46,560
So we add this to the stack and it does not have a left child.

101
00:05:46,560 --> 00:05:49,560
So only node six gets added to the stack.

102
00:05:49,560 --> 00:05:53,220
And we are again over here we see that the stack is not empty.

103
00:05:53,220 --> 00:05:54,930
So we pop from the stack.

104
00:05:54,930 --> 00:05:57,180
We add the value to the results array.

105
00:05:57,180 --> 00:06:02,280
And this node over here does not have a right child, but it does have a left child.

106
00:06:02,280 --> 00:06:04,530
So it gets added to the stack.

107
00:06:04,530 --> 00:06:06,030
And again we are over here.

108
00:06:06,030 --> 00:06:07,200
The stack is not empty.

109
00:06:07,200 --> 00:06:11,190
So we pop from the stack and we add the value to the results array.

110
00:06:11,190 --> 00:06:14,880
Again we come over here and at this point the stack is empty.

111
00:06:14,880 --> 00:06:15,780
So we are done.

112
00:06:15,780 --> 00:06:21,120
And notice that we have got the preorder traversal of the binary tree.

113
00:06:21,120 --> 00:06:23,670
And we have implemented this with this stack.

114
00:06:23,670 --> 00:06:29,730
And thus this is the iterative way for implementing the preorder traversal of a binary tree.