1
00:00:00,320 --> 00:00:01,340
Welcome back.

2
00:00:01,340 --> 00:00:07,460
Let's now implement the method that you have discussed in the previous video to traverse the given binary

3
00:00:07,460 --> 00:00:09,320
tree in a preorder manner.

4
00:00:09,320 --> 00:00:12,710
And again, as we have discussed, this is going to be the iterative solution.

5
00:00:12,710 --> 00:00:13,190
Okay.

6
00:00:13,190 --> 00:00:15,890
So we are given the root of the binary tree over here.

7
00:00:15,890 --> 00:00:20,600
And first itself we can check if the binary tree which is given to us is empty.

8
00:00:20,600 --> 00:00:24,440
And if that is the case then we will just return an empty array.

9
00:00:24,620 --> 00:00:25,160
Okay.

10
00:00:25,160 --> 00:00:26,390
Now let's proceed.

11
00:00:26,390 --> 00:00:32,150
And in the question notice it's mentioned that as we traverse the given binary tree, we will have to

12
00:00:32,150 --> 00:00:36,530
take the value of the nodes and add it to an array, and then finally return that array.

13
00:00:36,530 --> 00:00:40,430
So for that let's create an array which I'm calling rez.

14
00:00:40,430 --> 00:00:44,840
And as we traverse the binary tree we will be adding values to this array.

15
00:00:44,840 --> 00:00:48,440
And finally we will be returning this array okay.

16
00:00:48,440 --> 00:00:53,960
And as we have discussed in the previous video, we are going to use a stack for this solution.

17
00:00:53,960 --> 00:00:59,420
And initially we are going to fill the root of the tree which is given to us to the stack over here.

18
00:00:59,420 --> 00:00:59,930
Okay.

19
00:00:59,930 --> 00:01:02,390
And then we are going to have a while loop.

20
00:01:02,390 --> 00:01:07,370
And this will keep looping as long as something is there in the stack.

21
00:01:08,660 --> 00:01:13,550
So if there is something in the stack then we are going to pop from the stack.

22
00:01:13,550 --> 00:01:16,100
And when we pop, we are going to get a node.

23
00:01:16,100 --> 00:01:17,990
And let me store that over here.

24
00:01:17,990 --> 00:01:22,310
So let's say let node is equal to stack dot pop okay.

25
00:01:22,310 --> 00:01:23,810
So we're getting a node over here.

26
00:01:23,810 --> 00:01:29,210
And at this point we will push the value of this particular node to the results array.

27
00:01:29,210 --> 00:01:33,650
So I can say rest dot push node dot val okay.

28
00:01:33,650 --> 00:01:39,260
And then as we've discussed in the previous video, first we are going to check whether this particular

29
00:01:39,260 --> 00:01:41,030
node has a right child.

30
00:01:41,030 --> 00:01:44,780
And if it does we'll add that particular node to the stack.

31
00:01:44,780 --> 00:01:49,760
And again remember we are adding the node to the stack, not the value of that particular node to the

32
00:01:49,760 --> 00:01:50,090
stack.

33
00:01:50,090 --> 00:01:55,940
Because at a later point when we pop from the stack and get that node, we would want to check whether

34
00:01:55,940 --> 00:01:59,030
that particular node has a right and left child.

35
00:01:59,030 --> 00:01:59,420
Okay.

36
00:01:59,420 --> 00:02:01,130
So over here let's implement that.

37
00:02:01,130 --> 00:02:08,870
So if this particular node has a right child then we are going to push this particular node to the stack

38
00:02:08,870 --> 00:02:09,380
okay.

39
00:02:10,820 --> 00:02:14,690
And then we're going to check if this node has a left child.

40
00:02:15,080 --> 00:02:20,420
And if it does again we're going to push this particular node to the stack.

41
00:02:21,260 --> 00:02:22,250
And that's it.

42
00:02:22,250 --> 00:02:25,220
So this should help us solve this question okay.

43
00:02:25,220 --> 00:02:29,480
Now let's go ahead and run this code and see if it's passing all the test cases.

44
00:02:30,650 --> 00:02:32,270
And you can see that it's working.

45
00:02:32,270 --> 00:02:33,800
It's passing all the test cases.

46
00:02:33,800 --> 00:02:40,280
So this is how we can implement the preorder traversal for a binary tree in an iterative manner.