Series #2: The Remove Method
This is the second blogpost in a series on Binary Search Tree methods. In the last blogpost, we discussed what a Binary Search Tree is briefly and then we went through the Inserting a Node method and a Contains Value method and how to optimally code both of these methods in Python. In this blogpost, we are going to discuss a more complicated method, Removing a Node.
Before we dive into the Remove method, let’s briefly refresh on the properties of a Binary Search Tree (BST). Specifically, they have a value, and a left child and a right child (the children can be None/Null values). A left child is a left child node when the value in the child node is less than the value in the parent node. A right child is a right child node when the value in the child node is greater than or equal to the value in the parent node. Now let’s start building an efficient Remove Node method!
Similar to the last post, we are going to have our BST be constructed in a Python class with the three values we talked about in the previous paragraph: value, left child, and right child. This will look like this:
Now let’s build our Remove method. This method will take three parameters: the value that we want to remove, and the parent node (which will default to None/Null). It will also take in the self variable as it will be a BST class method. Our class method definition of remove will look like this:
Now we can start building out the actual remove functionality. We will start by creating a while loop that will loop until the node that we are currently at is None/Null. Our first priority is to check the comparison of the current node value and the input value that we would like to remove. If the input value is less than the current node value then we will want to set the parent node to the current node and will want to set the current node to the left child of the current node. We do this because the current node is greater than the input value, and thus our only chance in finding a match is to go to the left child (input value is less than the current node value). We will do the opposite when the input value is greater than the current node value, which is setting the parent node to the current node and setting the current node to the current node’s right child. We will then loop through the while loop again until we have either figured out that there is no match (null current node) or find a match. In the case that we find the match, we will want to run through multiple different scenarios so we know how to delete the node without ruining the BST. Here is what we have up to this point:
We are now going to code the multiple scenarios that we run into when we have found a node value that equal our input value. To start, we are going to check if the current node has no children, which is a straightforward scenario. If our matching current node does not have a left child or right child then we will find the smallest value of the right subtree and will use this to replace the current node, which we are removing, to this small value. After we have moved the right subtree’s smallest value then we will want to remove the right subtree’s smallest value node from that right subtree.
Now we will construct a helper class method, get_min_value, that will grab our right subtree’s smallest value. All this function is going to do is loop through the current node’s left child until it gets to the node’s leftest most child node value and it will return that value. Here is the helper method:
Now we can finish our no children scenario, which will look like this:
Next we are going to check whether the node that we want to remove is the root node, so we will see if there is a None/null parent node. Additionally, the assumption is made that there is only one child, left or right, if any, since we check in the previous if statement for both child nodes If there is, we will then check to see if the left child node is None/null. If it is, we will then set the left subtree to the root, where the left child node will be the root, and the right child (if applicable) of the left subtree will be the new right child, and the left child will be the new left child. If the left child node is None/null and the right child is not None/null, then we will do the opposite to what we did above. Lastly, if both are null, then we will do nothing and simply can just “pass” or skip this else altogether. The above logic can be seen here:
Our last two scenarios are relating to the positioning (left or right) of the current node. We check if it’s a right or left child by comparing the parent node’s left/right children to the current node. If the current node is a left child then we will set the parent node’s left child to the left child of the left child if applicable, otherwise we will set it to the right child of the current node. We will do the opposite if the current node that we want to remove is a right child, and will set the left child or right child (if there is no left child) to the parent node’s right child. This code can be see here:
Lastly, when we make it through the if conditions in the input value equals current node scenarios then we will break from the for loop and will return the self instance (this is so that we can curry class methods on top of calling the Remove method). The entire final Remove method code, including the class and the __init__ method, can be seen here:
This was the second part of a blog series on BST. I hope that you enjoyed this article and were able to learn a thing or two. Thank you for taking the time to read. In the next section we will look through different ways to traverse through a BST. Happy Coding!
