Learn

Now that we have a insertion and searching in our binary search tree, the next functionality we will add is data removal. As you can imagine, removing data from a BST is not just as simple as deleting a reference to a node, we need to do some background work.

In pseudocode, our algorithm runs like this:

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 value is less than or greater than the current node

3. When you value equals the current node’s data, check if it has two children, if not, that node is replaced with it’s 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. The smallest value on the right hand side is guaranteed to be larger than the value on the left so when we replace it, it keeps the rules of the BST. This value is also guaranteed to be a leaf node (no children), so we can set it to nil once we have swapped its value into the current node we are trying to remove.

We will build the helper function to find the smallest value on the right hand side of a tree. The function can be used to find the smallest value in in the whole tree, but we only need it for this particular function.

Instructions

Under the private functions, find the multiline comment that describes our helper function. Create a new private function, findMinimumValue(_:) that has a single parameter, node, a BinaryNode<T> with no argument label. The function should return T.

Inside the function body, add a return statement that returns node.data for now.

Above the return statement, add a new variable, currentNode and set it equal to node.

Create a while let loop that unwraps currentNode.leftChild as next, inside the loop, set currentNode equal to next.

Change the return statement to now return currentNode.data instead of node.data.

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?