‫So now we're going to write the code for our contains function and we're going to pick up where we left
‫off in the last video with all of the steps that we're going to use to write the code.
‫So I'll move these steps down to the bottom and we'll start our code out like this.
‫We're going to pass this the value that we're looking for, and that will return a boolean.
‫So we'll start with this line.
‫If root equals null pointer return false.
‫That is this situation where we have an empty tree.
‫And if the tree is empty, then obviously the value that we're looking for is not in the tree.
‫We'll do that with this line of code.
‫If root equals null pointer return false and then we'll remove that line and then we'll set temp to
‫be equal to root.
‫We'll do that like this and then we'll remove that.
‫And that gets us into our wild loop.
‫So you can write this while loop two different ways.
‫You could say while temp is not equal to null pointer or you could just say while temp.
‫And that conditional will be true.
‫As long as temp is pointing at a node and it will be false if it ever points to null pointer.
‫So we'll remove that.
‫And then inside of the while loop, we'll say if it's less than we're going to go left.
‫So we'll do that like this.
‫And let's say we're looking for the number 27.
‫27 is the value that we're looking for if it is less than temp value and in this case, 27 is less than
‫47, we'll set temp to be equal to temp left and that moves temp down here.
‫So I'll remove this tree and then we can remove this line and then we'll say else if it is greater,
‫then we'll go, right?
‫We'll do that like this.
‫So let's say the number we're looking for now is 82.
‫If that value is greater than temp value and 82 is greater than 47, we'll set temp to be equal to temp.
‫Right.
‫And that moves that down here and we can remove the tree and remove this line from the list.
‫So the last thing in the wild loop is if the value is equal, we will return true.
‫We'll do that like this and we can remove this line.
‫And then finally, if temp ever points to a null pointer, it breaks us out of this while loop and we
‫return false.
‫And that we can just move that up here below the while loop.
‫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
‫and we'll walk through this code looking for the number 27, which is in the tree.
‫And then we'll walk through the code looking for the number 17, which is not in the tree.
‫So we're going to start out with the number 27.
‫So we're going to begin by saying while temp, which is saying while temp is pointing to a node, this
‫conditional will be true.
‫And that will say if the value that we're looking for is less than temp value and we're looking for
‫27, so it is less, we're going to set temp to be equal to temp left, which moves this down and then
‫we run through the while loop again.
‫So temp is still pointing at a node.
‫So this is true.
‫And since we're looking for the node with a value of 27, this is the code that applies.
‫The value 27 is greater than temp value, which is 21.
‫So temp is equal to temp, right?
‫And that moves temp down here.
‫And then we run the wild loop again.
‫And now this is what applies because we have found the value that we're looking for and we return true.
‫So let's move back up here and look for the number 17, we'll say while temp.
‫And since this is pointing at a node, this will run.
‫And this is the code that gets run because 17 is less than 47.
‫So we set temp to be equal to temp left and then the while loop runs again.
‫This applies again because 17 is less than 21.
‫And temp gets moved down.
‫We run the while loop again.
‫This applies again because 17 is less than 18 and when we set temp to be equal to temp left.
‫It does this.
‫So then when we come back up to this line, the conditional is now false.
‫It breaks us out of the wild loop and we return false.
‫So now I'm going to drop this tree out and we're going to bring back our code.
‫And one of the things I wanted to point out about this code is that you don't actually need this line
‫here.
‫And if you do a Google search for how to do a contains function, a lot of times you will see this in
‫here.
‫But I want to show why we actually don't need it.
‫Remember, this line of code is for when we have an empty tree.
‫And if we have an empty tree, we want to return.
‫False.
‫So I'm going to remove this and show how this code, without that line will still work with an empty
‫tree.
‫So I'm going to bring this up and with this line of code we set temp to be equal to root and because
‫temp is now equal to null pointer, when we try to run the while loop, this conditional will be false.
‫That breaks us out of the while loop and then we come down here and return false.
‫The code will work either way, but this is a little bit cleaner, so I'll drop this out of here.
‫This is our final version of the contains function.
‫So we'll look at this code in a moment in V's code, and when we do, we'll build this tree.
‫So first we'll run contains on the number 27 and that is in the tree and that should return true.
‫And then we'll run contain on the number 17 and that should return false.
‫So now let's flip over and take a look at this.
‫So there is our contains member function added to our binary search tree class and I'll scroll up and
‫in our main function these lines of code create that binary search tree that we just looked at.
‫And then down here we're running contains on 27 and 17 and remember in C++, if you return, true,
‫it is a number one and if you return false, it's a zero.
‫So I'll run this and you can see that for the number 27 it returned.
‫True, and for 17 it returned false.
‫And that is our function for contains.