1
00:00:00,440 --> 00:00:05,510
‫So in this video we'll write the code for depth first search preorder.

2
00:00:05,870 --> 00:00:11,150
‫So I'll bring up a tree and we'll start our code off like this.

3
00:00:11,450 --> 00:00:16,760
‫So we're going to pass this a node and to begin with we're going to pass it the route.

4
00:00:17,000 --> 00:00:19,850
‫And remember that the route is private.

5
00:00:20,060 --> 00:00:25,160
‫So we're going to need a workaround to be able to pass the route to this function, if we're going to

6
00:00:25,160 --> 00:00:26,630
‫call it from Main.

7
00:00:26,750 --> 00:00:29,660
‫And we'll talk about that workaround in a moment.

8
00:00:30,080 --> 00:00:36,980
‫So the first thing we're going to do in this function is output the value of the current node.

9
00:00:37,370 --> 00:00:44,840
‫Then we're going to say if current node left and you could also write this as if current node left is

10
00:00:44,840 --> 00:00:54,020
‫not equal to null pointer, then we're going to call DFS preorder on current node left and this is where

11
00:00:54,020 --> 00:00:55,790
‫the function is recursive.

12
00:00:56,630 --> 00:00:59,630
‫And then we'll look to see if there's a node on the right.

13
00:00:59,630 --> 00:01:05,540
‫And if there is, we'll call DFS pre-order on current node, right?

14
00:01:05,930 --> 00:01:08,840
‫So now I'm going to show how we call this function.

15
00:01:08,840 --> 00:01:15,050
‫Given that the root is private, we do this by overloading the function.

16
00:01:15,350 --> 00:01:19,220
‫So notice that both functions have the same name.

17
00:01:19,220 --> 00:01:24,800
‫It's just that with the first one, we pass it in an argument and with the second one we don't.

18
00:01:25,010 --> 00:01:31,610
‫So from the main function, we're going to call this one, and this function will in turn call the other

19
00:01:31,610 --> 00:01:36,380
‫function and pass at the root, and that will run this function.

20
00:01:36,890 --> 00:01:42,470
‫So for now, I'm going to remove this last line and bring in a call stack.

21
00:01:42,860 --> 00:01:47,300
‫So we're calling this version of DFS pre-order with The Root.

22
00:01:47,300 --> 00:01:50,060
‫So I'm going to add this to the call stack.

23
00:01:50,060 --> 00:01:53,060
‫It is being called on that 47 node.

24
00:01:53,390 --> 00:01:58,430
‫So with that instance of the function, the first thing that we do is output the value.

25
00:01:58,430 --> 00:02:00,530
‫So we'll output that to the screen.

26
00:02:01,040 --> 00:02:08,000
‫And then we come down to here, if there's a node on the left and there is, we'll call DFES pre order

27
00:02:08,000 --> 00:02:09,680
‫on that node on the left.

28
00:02:09,680 --> 00:02:13,280
‫So now we're calling this on the 21 node.

29
00:02:13,580 --> 00:02:20,330
‫So now that instance that was called on the 21 node is the active instance on the call stack will output

30
00:02:20,330 --> 00:02:23,510
‫the value of the 21 node like this.

31
00:02:23,900 --> 00:02:25,910
‫And then we'll come down to here.

32
00:02:25,910 --> 00:02:32,390
‫And if there's an item on the left of the 21 node and there is the 18, now we're going to add an instance

33
00:02:32,390 --> 00:02:35,390
‫of pre order on the 18 node.

34
00:02:35,660 --> 00:02:41,000
‫The first thing we'll do with that is output the value of the 18 node like this.

35
00:02:41,450 --> 00:02:46,820
‫But the 18 node doesn't have anything on the left and it doesn't have anything on the right.

36
00:02:46,820 --> 00:02:50,720
‫So now it's done running and it will be popped from the call stack.

37
00:02:51,050 --> 00:02:56,060
‫So now the instance that was called on the 21 node is the active instance.

38
00:02:56,060 --> 00:02:58,160
‫It is already gone left.

39
00:02:58,160 --> 00:03:00,560
‫Now it's going to go right.

40
00:03:00,710 --> 00:03:04,040
‫So now we add an instance with a 27 node.

41
00:03:04,250 --> 00:03:09,050
‫Now for that instance, we'll run the first line and output the value.

42
00:03:09,140 --> 00:03:14,660
‫The 27 node doesn't have anything on the left or the right, so now it will be popped from the call

43
00:03:14,660 --> 00:03:15,290
‫stack.

44
00:03:15,590 --> 00:03:19,280
‫So now the instance with the 21 node is at the top of the call stack.

45
00:03:19,280 --> 00:03:25,640
‫It has gone left, it has gone right and it's done running and it will be popped from the call stack.

46
00:03:25,850 --> 00:03:30,020
‫Now, the instance on the 47 node is the active instance.

47
00:03:30,200 --> 00:03:32,090
‫It has already gone left.

48
00:03:32,120 --> 00:03:37,790
‫Now it will go right and we'll add an instance on that 76 node.

49
00:03:38,090 --> 00:03:45,320
‫So now we'll output the value from that node like that, and then we'll go left and call an instance.

50
00:03:45,320 --> 00:03:46,820
‫On the 52 node.

51
00:03:47,390 --> 00:03:54,530
‫The 52 node will output its value and it will look left and right, but it's a leaf node, so it's done

52
00:03:54,530 --> 00:03:57,590
‫running and it will be popped from the call stack.

53
00:03:57,890 --> 00:04:02,270
‫So now the instance called on the 76 node is the one that is active.

54
00:04:02,300 --> 00:04:03,680
‫It has gone left.

55
00:04:03,680 --> 00:04:08,150
‫Now it will go right and add an instance with the 82 node.

56
00:04:08,860 --> 00:04:11,680
‫The 82 node will output its value.

57
00:04:12,130 --> 00:04:17,800
‫It will look to the left and the right, but it is a leaf node, so that will be popped from the call

58
00:04:17,800 --> 00:04:18,430
‫stack.

59
00:04:18,640 --> 00:04:21,310
‫Now, the 76 is the active instance.

60
00:04:21,310 --> 00:04:22,420
‫It has gone left.

61
00:04:22,420 --> 00:04:23,320
‫It has gone right.

62
00:04:23,320 --> 00:04:25,690
‫So it will be popped from the call stack.

63
00:04:25,780 --> 00:04:29,980
‫And then finally, the instance that was called on the route, it has gone left.

64
00:04:29,980 --> 00:04:31,150
‫It has gone right.

65
00:04:31,150 --> 00:04:34,210
‫And now it will be popped from the call stack.

66
00:04:34,510 --> 00:04:38,950
‫And now all of the values from the tree have been output.

67
00:04:39,660 --> 00:04:46,110
‫So we'll look at this code in a moment and vs code remember we will be overloading this function when

68
00:04:46,110 --> 00:04:54,120
‫we look at this and when we do we'll build this tree and we'll run DFES pre order and we will expect

69
00:04:54,120 --> 00:04:56,130
‫this to be the output.

70
00:04:56,610 --> 00:04:59,880
‫So now let's flip over and take a look at this.

71
00:05:01,240 --> 00:05:09,250
‫So this is that first member function called DFS preorder that gets past a node and this is the second

72
00:05:09,250 --> 00:05:13,720
‫member function that has the same name but doesn't get past an argument.

73
00:05:14,020 --> 00:05:21,010
‫So I'm going to hover over this and it shows that there is one overload, so it'll show that this is

74
00:05:21,010 --> 00:05:22,630
‫an overloaded function.

75
00:05:23,110 --> 00:05:29,980
‫So I'm going to scroll down to our main function and this creates the binary search tree and this adds

76
00:05:29,980 --> 00:05:33,400
‫the nodes to make it look just like it did in the diagram.

77
00:05:33,520 --> 00:05:38,890
‫And with this line we'll run DFS preorder and I'll run this.

78
00:05:39,670 --> 00:05:44,590
‫And all of the values have been output in the order that we expected.

79
00:05:45,600 --> 00:05:51,030
‫And that is our member function for depth first search preorder.