1
00:00:02,090 --> 00:00:03,230
Welcome back.

2
00:00:03,230 --> 00:00:09,980
So this question is about implementing preorder traversal in an iterative way.

3
00:00:09,980 --> 00:00:18,230
So it says given the root of a binary tree, return the preorder traversal of its nodes values.

4
00:00:18,350 --> 00:00:18,950
Right.

5
00:00:18,950 --> 00:00:20,600
The iterative solution.

6
00:00:20,600 --> 00:00:24,140
So we have previously seen the recursive solution for this.

7
00:00:24,140 --> 00:00:28,070
But over here we are going to focus on the iterative solution.

8
00:00:28,070 --> 00:00:30,020
And we are given an example.

9
00:00:30,020 --> 00:00:35,030
If this is the binary tree which is given to us, this is the expected output.

10
00:00:35,030 --> 00:00:42,680
Now we know that in preorder traversal we first visit the root, then the left, and then the right

11
00:00:42,680 --> 00:00:44,210
of the particular node right.

12
00:00:44,210 --> 00:00:49,910
So if this is the binary tree which is given to us, we start over here which is the root.

13
00:00:49,910 --> 00:00:52,130
And that's why you have one over here.

14
00:00:52,130 --> 00:00:59,660
Then we go to the left of this particular node and we are at two now at this point two is the root.

15
00:00:59,660 --> 00:01:02,330
And because you have root over here we add two.

16
00:01:02,360 --> 00:01:04,670
Again we go left of two.

17
00:01:04,670 --> 00:01:06,290
So we come to this node.

18
00:01:06,290 --> 00:01:09,740
And because four is now the root we added over here.

19
00:01:09,740 --> 00:01:11,510
And then we try to go left.

20
00:01:11,510 --> 00:01:13,010
But there is nothing over here.

21
00:01:13,010 --> 00:01:14,630
And then we go right.

22
00:01:14,630 --> 00:01:16,430
And again you can see there is nothing over here.

23
00:01:16,430 --> 00:01:22,820
So at this point for this part we are done with the root and we are done with the left.

24
00:01:22,820 --> 00:01:24,530
And then we go right.

25
00:01:24,530 --> 00:01:27,620
So we come over here and we are at node five.

26
00:01:27,620 --> 00:01:30,080
Now node five is the root at this point.

27
00:01:30,080 --> 00:01:31,580
And we added over here.

28
00:01:31,580 --> 00:01:33,470
And then we go left.

29
00:01:33,470 --> 00:01:34,880
And we are at node seven.

30
00:01:34,880 --> 00:01:36,470
This is the root at this point.

31
00:01:36,470 --> 00:01:38,150
And this is also added over here.

32
00:01:38,150 --> 00:01:41,090
And then when we try to go left we don't have anything.

33
00:01:41,090 --> 00:01:43,760
And then we try to go right and we don't have anything.

34
00:01:43,760 --> 00:01:49,490
So at this point we are done with root and we are done with the left of it for this part.

35
00:01:49,490 --> 00:01:51,500
And we don't have anything in the right.

36
00:01:51,500 --> 00:01:59,360
So at this point we can return and notice that we are done with this root, and its left part is also

37
00:01:59,360 --> 00:02:00,050
covered.

38
00:02:00,050 --> 00:02:03,950
Now we go to the right and we are at node three.

39
00:02:03,950 --> 00:02:06,320
And node three at this point is the root.

40
00:02:06,320 --> 00:02:11,660
So we add it over here because always we do root then left node and then right node.

41
00:02:11,660 --> 00:02:13,310
And then we try to go to the left.

42
00:02:13,310 --> 00:02:14,660
But there is nothing over here.

43
00:02:14,660 --> 00:02:17,570
So we go to the right and we are at node six.

44
00:02:17,570 --> 00:02:19,640
Now node six is the root node.

45
00:02:19,640 --> 00:02:21,800
So it has to be added to the results array.

46
00:02:22,550 --> 00:02:24,470
And then we come to node eight.

47
00:02:24,470 --> 00:02:27,110
And we added over here because it's the root at this point.

48
00:02:27,110 --> 00:02:29,600
So this is how we get this output.

49
00:02:29,990 --> 00:02:37,100
So the preorder traversal of any binary tree is obtained by first visiting the root node.

50
00:02:38,120 --> 00:02:39,110
So you have one.

51
00:02:39,110 --> 00:02:41,180
And then we go to the left.

52
00:02:41,180 --> 00:02:41,960
So you have two.

53
00:02:41,960 --> 00:02:43,190
And then you go to the right.

54
00:02:43,190 --> 00:02:44,600
So you have three okay.

55
00:02:44,600 --> 00:02:48,440
Now it's important to understand how the values get added over here.

56
00:02:48,440 --> 00:02:54,560
So when we are at this node remember this is the root node in that particular instance.

57
00:02:54,560 --> 00:02:56,090
So that's how we add one.

58
00:02:56,090 --> 00:02:58,790
And then we go to the left.

59
00:02:58,790 --> 00:03:03,020
So we are over here and we are going to consider this subtree.

60
00:03:03,020 --> 00:03:04,280
Whatever is there over here.

61
00:03:04,280 --> 00:03:06,230
And at this point this is the root.

62
00:03:06,230 --> 00:03:08,240
And that's why we can add two over here.

63
00:03:08,240 --> 00:03:10,880
And then we try to go left or to the right.

64
00:03:10,880 --> 00:03:15,890
And once we're done with this we are done with the root and we are done with the left part.

65
00:03:15,890 --> 00:03:17,900
And then we visit the right part.

66
00:03:17,900 --> 00:03:20,720
And over here we have to add three to the results array.

67
00:03:20,990 --> 00:03:23,420
So this is something that we have previously seen.

68
00:03:23,420 --> 00:03:26,450
But I'm just quickly reviewing this concept.

69
00:03:26,450 --> 00:03:31,970
Now in the next video let's discuss how we can implement this solution in an iterative.