Wow, what a big tree.
Would be a shame if someone removed one of it’s…nodes…
What makes node removal particularly difficult are the number of edge cases involved. Until now all of the operations I had done on trees and binary search trees were fairly simple. A couple conditional statements checking values or pushing values into lists and making recursive calls or using a queue. As you’ll see node removal requires a tree of it’s own; a tree of if-else statements to check for all of these different edge cases.
Adding a helper method
We start out with a method and it’s helper. The helper method takes in a value and a BST node called “parent”. This will be useful for the case of trying to remove the root node (specifically when the root does not have a left AND right child).
Finding the right value
First we include if statements to check if the value is less or more than the value of the current node that we called the remove method on. If either is true and that respective child is not null we recursively call our remove method on that child, pass it the original value and also pass the current node as the parent.
All the edge cases
This else statement is where we go if the value passed in as an argument matches the value of the current node. Within it are four different cases:
- The current node has a left and a right child.
- The current node does not have a parent (is the root node) and does not have two children.
- The current node is the left child of its parent.
- The current node is the right child of its parent.
Let’s go through these one by own (and maybe skip one for a sec).
1. The current node has a left and a right child
In this first case the node to be removed has both a left and a right child. To better understand this, let’s visualize an example of a BST:
Say that the node we are trying to remove is the node holding the value 27, coincidentally the root node. Since this the root node and has two children we can’t really just remove it — there still needs to be a node there. But what value do we keep there? There is only one value in the tree that can replace it and still maintain the BST principle (each node’s value is greater than all the nodes to its left and less than all the nodes to its right). The answer is the left-most node in the right child’s tree. In our example you can see that if we remove the 27 node we can replace that node’s value with the node containing the value 31. After that we just need to remove the original node holding 31 since it has been “moved” to the root. We do that by calling remove on the right sub-tree and passing it the value we just saved for the root node (31) as well as the current node as its parent.
In order to find the left-most node of the right sub-tree we employ a helper method called getMinValue. Here is that method:
The method checks if the current node has a left child. If it doesn’t it returns the current node’s value, but if it does it recursively calls getMinValue on its left child until it gets to the left-most leaf node.
2. The current node does not have a parent (is the root node) and does not have two children
Adding on to the previous if statement, we hit this case when we’re trying to remove the root node but it only has either a left or a right child. In line 5 we check to see if the only child is a left node. If so we replace the current node’s (the root’s) value with the value of the left node, set the current node’s right child to the right child of the left node and then finally set the current node’s left child to the left child of the left node. We do the same operation for if the right child is the only child except reversed.
This caused me a little confusion. Refer back to the example of the Binary Search Tree above. Imagine that the right sub-tree starting at node 35 didn’t exist and we wanted to remove the root node. In order to do so we essentially need to put node 14 as the root and it’s left and right children in their respective places.
The final else statement is blank because there is nothing to do in that case. I tried to set the current node’s value to null but Java did not like that so the best solution I found was to do absolutely nothing.
3. The current node is the left child of its parent
In this case the node to be removed is the left child of its parent (also it does not have both left and right children and it is not the root node).
This case starts at line 16. We are checking to see if the parent node’s left node is the current node (the node to be removed). If it is we have a fun little ternary operator to help us. If the current node has a left child we set the parent’s left child to that node and if not we set the parent’s left child to be the current node’s right child.
Going back to our example, let’s say that we want to remove node 10. In this case we are going to try to replace this node with either it’s left or right child. Even if it has no children like in our example, the parent’s left child will be set to null and we have successfully removed the node.
4. The current node is the right child of its parent
This is the same as the previous example except if the node to be removed is the right child of its parent.
As you can see from line 19, we still check to see if the node to be removed has a left child to replace it first.
The Full Solution
Like I mentioned in the beginning, this operation was more involved than the methods I’d written for binary search trees before. Hopefully this helps you understand all the edge cases present when trying to remove a node from a BST.