1
00:00:00,430 --> 00:00:05,190
‫So now we're going to write the code for depth first search in order.

2
00:00:05,200 --> 00:00:09,850
‫So I'm going to bring up a tree and we'll start our code off like this.

3
00:00:10,270 --> 00:00:16,480
‫And just like last time, I'm going to start out with the code for depth first search preorder where

4
00:00:16,480 --> 00:00:24,130
‫the sea out statement came first and then we did depth first search post order where the sea out statement

5
00:00:24,130 --> 00:00:25,750
‫came last.

6
00:00:25,900 --> 00:00:32,710
‫And as you may have guessed for depth first search in order, the sea out statement is in the middle

7
00:00:32,920 --> 00:00:39,970
‫and once again we'll kick this off like this where we overload the function and then call this with

8
00:00:39,970 --> 00:00:40,780
‫the root.

9
00:00:41,110 --> 00:00:46,540
‫So I'm going to remove this last line, bring in the call stack, and we're going to call this on the

10
00:00:46,540 --> 00:00:50,620
‫root to begin with, and I'll add that to the call stack.

11
00:00:50,920 --> 00:00:59,620
‫So this instance of the function will run this and add an additional instance called on the 21 node.

12
00:00:59,890 --> 00:01:05,530
‫Now this instance is going to call an instance of the function with the 18 node.

13
00:01:05,800 --> 00:01:12,610
‫So this last instance that was called on the 18 node will run this if statement and because it doesn't

14
00:01:12,610 --> 00:01:18,490
‫have a node on the left, it will move down to this line of code and output its value.

15
00:01:18,790 --> 00:01:20,410
‫Then it will look to the right.

16
00:01:20,410 --> 00:01:26,230
‫And because there is no node on the right of the 18 node, it is done running and this will be popped

17
00:01:26,230 --> 00:01:27,550
‫from the call stack.

18
00:01:27,910 --> 00:01:32,140
‫So now the instance called on the 21 node is the active instance.

19
00:01:32,140 --> 00:01:33,490
‫It went left.

20
00:01:33,640 --> 00:01:41,680
‫Now it will output its value and then it will go right and we'll add an instance with the 27 node.

21
00:01:42,100 --> 00:01:49,840
‫The 27 node will look left, it will output its value like this, and then it will look right and then

22
00:01:49,840 --> 00:01:52,120
‫it will be popped from the call stack.

23
00:01:52,540 --> 00:02:00,010
‫So now the instance with a 21 node has gone left, output its value and has gone right now it will be

24
00:02:00,010 --> 00:02:02,380
‫popped from the call stack as well.

25
00:02:02,680 --> 00:02:07,870
‫So now the instance that was called On the Root is the active instance on the call stack.

26
00:02:07,870 --> 00:02:08,950
‫It went left.

27
00:02:08,950 --> 00:02:16,780
‫Now it will output its value like this and then it will go right and that'll add an instance called

28
00:02:16,780 --> 00:02:18,520
‫on the 76 node.

29
00:02:18,850 --> 00:02:24,340
‫Now the 76 node is going to go left and add an instance with the 52 node.

30
00:02:24,640 --> 00:02:27,190
‫The 52 node will look left.

31
00:02:27,220 --> 00:02:35,500
‫It will output its value like this, and then it will look right and then it will be popped from the

32
00:02:35,500 --> 00:02:36,430
‫call stack.

33
00:02:36,760 --> 00:02:41,650
‫So now the instance that was called on the 76 node has gone left.

34
00:02:41,650 --> 00:02:47,650
‫Now it can output its value like this and now it can go right.

35
00:02:47,800 --> 00:02:50,650
‫So now we'll call an instance on the 82 node.

36
00:02:51,070 --> 00:02:52,810
‫It is going to look left.

37
00:02:52,990 --> 00:02:56,170
‫It will output its value like this.

38
00:02:56,620 --> 00:02:57,790
‫It will look right.

39
00:02:57,790 --> 00:03:01,180
‫And once it does this, it will be popped from the call stack.

40
00:03:01,570 --> 00:03:04,480
‫So now the instance called on the 76 node.

41
00:03:04,480 --> 00:03:08,230
‫It has gone left, printed out its value and it has gone right.

42
00:03:08,230 --> 00:03:10,510
‫So it will be popped from the call stack.

43
00:03:10,750 --> 00:03:14,560
‫The same is true of the instance called on the 47 node.

44
00:03:14,560 --> 00:03:17,800
‫So that will be part from the call stack as well.

45
00:03:18,190 --> 00:03:24,370
‫And now all of the values from the binary search tree have been output in order.

46
00:03:24,910 --> 00:03:31,030
‫So we'll look at this code in a moment in VZ code along with the overloaded function.

47
00:03:31,210 --> 00:03:38,590
‫And when we do will create this tree and we'll run depth first search in order and we'll expect the

48
00:03:38,590 --> 00:03:40,600
‫output to look like this.

49
00:03:40,960 --> 00:03:44,200
‫So now let's flip over and take a look at this.

50
00:03:44,980 --> 00:03:50,230
‫So that's the depth first search in order function that we just walked through.

51
00:03:50,500 --> 00:03:52,420
‫And then remember this as overloaded.

52
00:03:52,420 --> 00:03:54,760
‫So we have this version here.

53
00:03:55,560 --> 00:03:57,390
‫And I'll scroll up.

54
00:03:57,690 --> 00:03:58,110
‫So what?

55
00:03:58,110 --> 00:04:03,930
‫Our main function, this creates our binary search tree and this creates the nodes just the way they

56
00:04:03,930 --> 00:04:06,400
‫were in the diagram that we just saw.

57
00:04:06,420 --> 00:04:12,390
‫And then with this line, we'll run depth first search in order, and I'll run this.

58
00:04:12,900 --> 00:04:20,850
‫And this gives us the output that we were expecting in numerical order and that is our member function

59
00:04:20,880 --> 00:04:21,780
‫for depth.

60
00:04:21,780 --> 00:04:24,180
‫First search in order.