Learn

We’ve solved step 4 of our pseudocode algorithm, let’s review the code again to finish implementing our remove functions.

1. Check if the node passed into the function exists, if not, return nil
2. Check the value we are looking for against the current node’s data
   - Recurse down either the left or right child depending on if the value is less than or greater than the current node
3. When your value equals the current node’s data, check if it has two children, if not, that node is replaced with its only child
4. If it has two children, find the smallest value on the right side and replace the current node’s value with that, and setting the smallest right-hand node to nil.

Similar to our previous design patterns, this logic will be contained in a private remove method and the user will have a public remove method that simply accepts a value to remove from the tree.

Instructions

In the private functions area, find the multiline comment that describes what we are trying to build. Under it, create a new private function, remove(_:fromParent:), that has two parameters, value of type T with no argument label and node, an optional BinaryNode<T> with an argument label, fromParent. This function will also return an optional BinaryNode<T>.

Inside the function body, return node for now so that the code compiles.

Above the return statement, add a guard-let statement that unwraps parent from node or else returns nil.

Change the return node statement to now return parent.

Next, let’s use a switch statement to compare the value against the node’s data.

Above the return statement, create a switch statement on value. Inside the switch add the following default case:

default: fatalError("Unexpected value")

We will be checking three different cases inside the switch statement.

Above the default, add a case that checks whether the value is less than parent.data. If so, assign parent.leftChild to remove(_:fromParent:) passing in value and parent.leftChild.

Add another case that checks if value is greater than parent.data. If it is, assign parent.rightChild to remove(_:fromParent:) passing in value and parent.rightChild.

The last case checks if value equals parent.data. Inside this case, set up an if statement with the following structure:

If parent.leftChild equals nil, return parent.rightChild
Else if, parent.rightChild equals nil, return parent.leftChild`
Else, set parent.data equal to the smallest value on the right hand side of the tree (use the helper function findMinimumValue(_:), passing in parent.rightChild!). Assign parent.rightChild to remove(_:fromParent:) passing in parent.data and parent.rightChild.

With the private remove(_:fromParent) function complete, we can now implement the public remove(_:) function. Under the appropriate comment, define a new function remove(_:) that takes a single parameter, value, of type T, with an omitted argument label.

Inside the function, make a call to the private remove(_:fromParent) function, passing in value and starting at root.

Great work! Our method is now complete, try calling the new remove(_:) method at the bottom of the file and make sure you don’t get any errors. In the next exercise, we’ll implement print functionality so we can see our hard work in action.

Take this course for free

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?