Our implementation of a searching function will provide the user with a boolean value as to whether the value is in the tree or not. Since it provides the user with this type of answer, we will call the function contains(_:). Similar to how the add function we created was implemented, we will have a private variation, contains(_:startingAt:) that will do the heavy lifting (recursion) behind the scenes.
Since this private function will use a standard recursive algorithm, let’s talk about our base case:
- When the node we are searching is nil, that is we’ve searched all the way to the end of a tree and can’t find the element, we will return false.
- If we reach a node that is not nil and its value is neither less than or greater than the value, it must equal the value and we return true.
If we don’t reach a base case, call the function on the left child if the value is less than the parent or the right child if it is greater than the parent.
The public function will take a value from the user and simply call the private function beginning at the root of the tree.
Instructions
We’ll begin the private function first. Below the multiline comment for contains in the private functions area, create a new function, contains(_:startingAt:) that has two parameters, value of type T with no argument label, and node of which will be a BinaryNode<T> optional and labeled startingAt. The function will return a Bool. Inside the function body, return false.
Inside the function, above the return statement, create a guard-let statement. It should unwrap node as parent. In the else clause it should return false.
This statement is responsible for handling our first base case, getting to a non-existent node.
Underneath the guard-let statement, create a new variable, valueFound and set it equal to false.
Change the return statement at the end of the function from false to valueFound.
Between valueFounds declaration/initialization and the return statement you will create an if-else statement that will run our recursive logic and final base case:
ifthevalueis less than theparent’sdata,valueFoundwill equal the result of callingcontainson thevalue, starting at theparent’s left child.else-ifthevalueis greater than theparent’sdata,valueFoundwill equal the result of callingcontainson thevalue, starting at theparent’s right child.else, we’ve found the value andvalueFoundequalstrue.
Below the comments for contains in the public functions section, create a new function, contains(_:) that has one parameter, value of type T, it should omit an argument label. The function returns a Bool.
Inside the function body, call the private contains(_:startingAt:) function we just created, passing in value and root.
With our contains functions complete, add a few more numbers of your choosing to the numberTree at the bottom of the file and make a few calls to your public contains(_:) function. Make sure to wrap the function call inside a print statement so you can see the result.