1
00:00:00,480 --> 00:00:06,540
‫So now we'll create our contains function and just like we had with our insert function, we're going

2
00:00:06,540 --> 00:00:10,200
‫to start with a video where we walk through all of the steps.

3
00:00:10,200 --> 00:00:12,030
‫That's what this video is.

4
00:00:12,150 --> 00:00:16,770
‫And then in the next video we'll use those steps to write the code.

5
00:00:17,190 --> 00:00:22,170
‫So with this function, we just want to see if a particular value is in our tree.

6
00:00:22,440 --> 00:00:26,880
‫So if we're looking for the number 27, the tree does have a 27.

7
00:00:26,880 --> 00:00:28,470
‫So we would return.

8
00:00:28,470 --> 00:00:29,310
‫True.

9
00:00:29,460 --> 00:00:35,850
‫But if we were looking for the number 17, the tree does not have a number 17, so it should return

10
00:00:35,850 --> 00:00:39,090
‫false if we have an empty tree.

11
00:00:39,090 --> 00:00:43,620
‫Obviously whatever value we're looking for is not in the tree.

12
00:00:43,920 --> 00:00:47,130
‫So this becomes the first item on our list.

13
00:00:47,430 --> 00:00:51,600
‫We'll say if root is equal to null pointer return false.

14
00:00:52,110 --> 00:00:54,270
‫Now let's bring back our tree.

15
00:00:54,600 --> 00:01:00,450
‫And just like we saw with our insert function, we need to have a variable that we can use to traverse

16
00:01:00,450 --> 00:01:01,380
‫through the tree.

17
00:01:01,620 --> 00:01:03,210
‫We'll call that temp.

18
00:01:03,330 --> 00:01:12,690
‫And if we're looking for the number 27, we will compare 27 against 47 and go left and then 27 is greater

19
00:01:12,690 --> 00:01:15,300
‫than 21 and that we would go right.

20
00:01:15,300 --> 00:01:20,400
‫And then finally we see that this is the number we're looking for and we would return.

21
00:01:20,400 --> 00:01:21,240
‫True.

22
00:01:21,720 --> 00:01:24,300
‫So let's bring this back up to the top.

23
00:01:24,390 --> 00:01:30,300
‫We'll add this to the list that we're going to create a variable temp that we set equal to root.

24
00:01:30,690 --> 00:01:35,670
‫So now let's look at a situation where we're looking for a number that is not in the tree.

25
00:01:36,060 --> 00:01:38,640
‫Let's say we're looking for the number 17.

26
00:01:38,910 --> 00:01:41,400
‫It is less than so we'll go left.

27
00:01:41,400 --> 00:01:42,930
‫It's less than 21.

28
00:01:42,930 --> 00:01:46,410
‫We go left again and it's less than 18.

29
00:01:46,410 --> 00:01:48,630
‫So we go left again.

30
00:01:48,630 --> 00:01:51,810
‫So now temp is equal to null pointer.

31
00:01:52,020 --> 00:01:58,980
‫And if this ever happens, we want to break out of our wild loop that we're using to traverse through

32
00:01:58,980 --> 00:01:59,820
‫the tree.

33
00:02:00,150 --> 00:02:06,690
‫So we'll say while temp is not equal to null pointer, so we'll keep iterating through this as long

34
00:02:06,690 --> 00:02:14,130
‫as we don't have this condition happen as we are traversing through this tree inside of this wild loop,

35
00:02:14,130 --> 00:02:15,990
‫we have a few possibilities.

36
00:02:16,590 --> 00:02:23,220
‫Either the number we are looking for is less than the node we're comparing it to and will go left.

37
00:02:23,960 --> 00:02:25,430
‫Or it's greater than.

38
00:02:25,430 --> 00:02:26,000
‫And we'll go.

39
00:02:26,000 --> 00:02:26,780
‫Right.

40
00:02:27,500 --> 00:02:31,220
‫Or its equal and will return true.

41
00:02:31,890 --> 00:02:34,290
‫And then there's a fourth possibility.

42
00:02:34,710 --> 00:02:42,300
‫And that fourth possibility is we have this scenario where it is equal to null pointer, in which case

43
00:02:42,300 --> 00:02:44,280
‫we return false.

44
00:02:44,760 --> 00:02:48,810
‫So these are all of the steps for the contains function.

45
00:02:49,200 --> 00:02:54,450
‫We'll pick up right here in the next video where we use these steps to code this.

46
00:02:54,960 --> 00:02:59,610
‫But for now, that is our intro to contains.