1
00:00:00,410 --> 00:00:06,290
‫So now we're going to write the code for our contains function and we're going to pick up where we left

2
00:00:06,290 --> 00:00:12,560
‫off in the last video with all of the steps that we're going to use to write the code.

3
00:00:12,800 --> 00:00:17,660
‫So I'll move these steps down to the bottom and we'll start our code out like this.

4
00:00:17,870 --> 00:00:23,900
‫We're going to pass this the value that we're looking for, and that will return a boolean.

5
00:00:24,380 --> 00:00:26,150
‫So we'll start with this line.

6
00:00:26,150 --> 00:00:30,050
‫If root equals null pointer return false.

7
00:00:30,350 --> 00:00:34,370
‫That is this situation where we have an empty tree.

8
00:00:34,550 --> 00:00:39,920
‫And if the tree is empty, then obviously the value that we're looking for is not in the tree.

9
00:00:40,160 --> 00:00:42,440
‫We'll do that with this line of code.

10
00:00:42,440 --> 00:00:51,260
‫If root equals null pointer return false and then we'll remove that line and then we'll set temp to

11
00:00:51,260 --> 00:00:52,630
‫be equal to root.

12
00:00:52,640 --> 00:00:57,230
‫We'll do that like this and then we'll remove that.

13
00:00:57,410 --> 00:01:00,110
‫And that gets us into our wild loop.

14
00:01:00,350 --> 00:01:03,050
‫So you can write this while loop two different ways.

15
00:01:03,050 --> 00:01:09,680
‫You could say while temp is not equal to null pointer or you could just say while temp.

16
00:01:09,950 --> 00:01:11,990
‫And that conditional will be true.

17
00:01:11,990 --> 00:01:18,320
‫As long as temp is pointing at a node and it will be false if it ever points to null pointer.

18
00:01:18,650 --> 00:01:20,690
‫So we'll remove that.

19
00:01:20,840 --> 00:01:26,900
‫And then inside of the while loop, we'll say if it's less than we're going to go left.

20
00:01:27,290 --> 00:01:29,360
‫So we'll do that like this.

21
00:01:29,360 --> 00:01:32,390
‫And let's say we're looking for the number 27.

22
00:01:32,390 --> 00:01:41,870
‫27 is the value that we're looking for if it is less than temp value and in this case, 27 is less than

23
00:01:41,870 --> 00:01:49,370
‫47, we'll set temp to be equal to temp left and that moves temp down here.

24
00:01:49,730 --> 00:01:57,800
‫So I'll remove this tree and then we can remove this line and then we'll say else if it is greater,

25
00:01:57,800 --> 00:01:59,570
‫then we'll go, right?

26
00:02:00,050 --> 00:02:02,030
‫We'll do that like this.

27
00:02:02,330 --> 00:02:06,560
‫So let's say the number we're looking for now is 82.

28
00:02:06,920 --> 00:02:17,570
‫If that value is greater than temp value and 82 is greater than 47, we'll set temp to be equal to temp.

29
00:02:17,570 --> 00:02:18,380
‫Right.

30
00:02:18,710 --> 00:02:25,940
‫And that moves that down here and we can remove the tree and remove this line from the list.

31
00:02:26,270 --> 00:02:34,220
‫So the last thing in the wild loop is if the value is equal, we will return true.

32
00:02:34,250 --> 00:02:38,900
‫We'll do that like this and we can remove this line.

33
00:02:39,290 --> 00:02:46,100
‫And then finally, if temp ever points to a null pointer, it breaks us out of this while loop and we

34
00:02:46,100 --> 00:02:47,990
‫return false.

35
00:02:48,660 --> 00:02:52,140
‫And that we can just move that up here below the while loop.

36
00:02:52,500 --> 00:03:00,390
‫So what I'm going to do now is just focus in on the while loop down, and then we'll bring up a tree

37
00:03:00,390 --> 00:03:05,280
‫and we'll walk through this code looking for the number 27, which is in the tree.

38
00:03:05,610 --> 00:03:11,250
‫And then we'll walk through the code looking for the number 17, which is not in the tree.

39
00:03:11,640 --> 00:03:14,820
‫So we're going to start out with the number 27.

40
00:03:15,210 --> 00:03:21,420
‫So we're going to begin by saying while temp, which is saying while temp is pointing to a node, this

41
00:03:21,420 --> 00:03:23,220
‫conditional will be true.

42
00:03:23,920 --> 00:03:30,400
‫And that will say if the value that we're looking for is less than temp value and we're looking for

43
00:03:30,400 --> 00:03:39,100
‫27, so it is less, we're going to set temp to be equal to temp left, which moves this down and then

44
00:03:39,100 --> 00:03:41,380
‫we run through the while loop again.

45
00:03:41,680 --> 00:03:43,720
‫So temp is still pointing at a node.

46
00:03:43,720 --> 00:03:44,950
‫So this is true.

47
00:03:45,130 --> 00:03:51,670
‫And since we're looking for the node with a value of 27, this is the code that applies.

48
00:03:52,030 --> 00:03:57,100
‫The value 27 is greater than temp value, which is 21.

49
00:03:57,430 --> 00:03:59,950
‫So temp is equal to temp, right?

50
00:04:00,810 --> 00:04:02,970
‫And that moves temp down here.

51
00:04:03,420 --> 00:04:06,390
‫And then we run the wild loop again.

52
00:04:06,390 --> 00:04:14,610
‫And now this is what applies because we have found the value that we're looking for and we return true.

53
00:04:15,220 --> 00:04:22,180
‫So let's move back up here and look for the number 17, we'll say while temp.

54
00:04:22,540 --> 00:04:25,690
‫And since this is pointing at a node, this will run.

55
00:04:26,020 --> 00:04:31,600
‫And this is the code that gets run because 17 is less than 47.

56
00:04:32,050 --> 00:04:38,850
‫So we set temp to be equal to temp left and then the while loop runs again.

57
00:04:38,860 --> 00:04:43,210
‫This applies again because 17 is less than 21.

58
00:04:43,570 --> 00:04:45,670
‫And temp gets moved down.

59
00:04:45,850 --> 00:04:48,580
‫We run the while loop again.

60
00:04:48,610 --> 00:04:57,340
‫This applies again because 17 is less than 18 and when we set temp to be equal to temp left.

61
00:04:58,150 --> 00:04:59,380
‫It does this.

62
00:04:59,830 --> 00:05:05,410
‫So then when we come back up to this line, the conditional is now false.

63
00:05:05,710 --> 00:05:10,960
‫It breaks us out of the wild loop and we return false.

64
00:05:11,690 --> 00:05:16,340
‫So now I'm going to drop this tree out and we're going to bring back our code.

65
00:05:16,670 --> 00:05:24,410
‫And one of the things I wanted to point out about this code is that you don't actually need this line

66
00:05:24,410 --> 00:05:25,130
‫here.

67
00:05:25,550 --> 00:05:31,250
‫And if you do a Google search for how to do a contains function, a lot of times you will see this in

68
00:05:31,250 --> 00:05:31,760
‫here.

69
00:05:32,180 --> 00:05:35,480
‫But I want to show why we actually don't need it.

70
00:05:35,930 --> 00:05:39,650
‫Remember, this line of code is for when we have an empty tree.

71
00:05:39,830 --> 00:05:42,650
‫And if we have an empty tree, we want to return.

72
00:05:42,650 --> 00:05:43,490
‫False.

73
00:05:43,850 --> 00:05:49,850
‫So I'm going to remove this and show how this code, without that line will still work with an empty

74
00:05:49,850 --> 00:05:50,240
‫tree.

75
00:05:50,240 --> 00:05:57,920
‫So I'm going to bring this up and with this line of code we set temp to be equal to root and because

76
00:05:57,920 --> 00:06:04,760
‫temp is now equal to null pointer, when we try to run the while loop, this conditional will be false.

77
00:06:05,060 --> 00:06:10,670
‫That breaks us out of the while loop and then we come down here and return false.

78
00:06:11,210 --> 00:06:18,880
‫The code will work either way, but this is a little bit cleaner, so I'll drop this out of here.

79
00:06:18,890 --> 00:06:22,970
‫This is our final version of the contains function.

80
00:06:23,420 --> 00:06:30,410
‫So we'll look at this code in a moment in V's code, and when we do, we'll build this tree.

81
00:06:30,620 --> 00:06:38,960
‫So first we'll run contains on the number 27 and that is in the tree and that should return true.

82
00:06:39,260 --> 00:06:45,980
‫And then we'll run contain on the number 17 and that should return false.

83
00:06:46,550 --> 00:06:49,730
‫So now let's flip over and take a look at this.

84
00:06:50,380 --> 00:06:59,020
‫So there is our contains member function added to our binary search tree class and I'll scroll up and

85
00:06:59,020 --> 00:07:04,720
‫in our main function these lines of code create that binary search tree that we just looked at.

86
00:07:04,990 --> 00:07:14,590
‫And then down here we're running contains on 27 and 17 and remember in C++, if you return, true,

87
00:07:14,620 --> 00:07:18,850
‫it is a number one and if you return false, it's a zero.

88
00:07:19,090 --> 00:07:24,280
‫So I'll run this and you can see that for the number 27 it returned.

89
00:07:24,280 --> 00:07:28,120
‫True, and for 17 it returned false.

90
00:07:28,920 --> 00:07:32,970
‫And that is our function for contains.