Removing Binary Search Tree Node -JavaScript

A binary search tree is a tree where all of the sibling nodes to the left of a parent node have a value less than the value of the parent node and all of the sibling nodes to the right of a parent node have a value greater than or equal to the value of the parent node.

In the diagram above, all of the siblings to the right of the root node have a value greater than the root node (10, 14 and 13 are greater than 8) and all of the siblings to the left have a value less than (3, 1, 6, 4 and 7 are less than 8). The trend is also applicable to the other parent nodes as you move further down the tree (1 is less than 3 and 6 six is greater than 3. Also all of the siblings of 6, which is to the right of 3, have values greater than 3).

If we wanted to remove a value from somewhere in the tree we would still need to maintain this hierarchy. The way to do this is to find the lowest value of all the siblings on the right side of the node and replace the the node we want to remove with that node. For example, if we wanted to remove the 3 from the above tree, we find the lowest value to right of it (which is 4), remove the 3 and put the 4 in its place. This maintains the binary search structure because 1 is less than 4 and both 6 and 7 are greater than 4.

The first step in this process is to actually find the node they we want to remove. We do this by traversing through the tree until our target node is found. Because we are working with a binary search tree we don’t have to search through the entire tree. At each node, if our target node has a value that is greater than the node we are currently on, we just go right and we can disregard all the sibling nodes to the left. The same is applicable if the target node is less than our current node (disregard all the siblings to the right).

In our remove method we want to have 2 parameters. The value we want to remove and the parent node. The parent node parameter is so we can keep track of what the parent node is. This is initially set to null in case we want to remove the root node, which does not have a parent.

Inside of the method we want to assign a variable to the current node. We can do this by assigning the variable to “this” when working inside of a class. We can use a while loop to traverse through the tree. If the target doesn’t equal the the current node we assign the current node to the parent variable and assign the right node to the current variable if the target is greater or assign the left node if the target is less than.

Next we need to address what to do once we find the target node. We have to find the lowest value of the siblings to the right of the node we want to remove, so we can do this using a helper method. In the helper method we will use a while loop to traverse to the next left node until we get to the last leaf and return its value.

The first case we want to account for is if our target node has both right and left siblings. This is where we would use our helper method, which we will call on the target’s right sibling. Once we have that value, we assign it to the target node which replaces its current value. We then want to call our remove method on the right siblings of our target to remove the node that has the new value. For example, when we replaced the 3 with the 4 in the above tree, we now want to remove the 4 from being a sibling of the 6.

Next we want to account for if the target node is the root of the tree and only has one direct sibling. If the root only has left siblings, then we assign the first left sibling’s value as the root’s new value and assign its siblings as the root’s new direct siblings. We do the same if it only has right siblings. If the target node is the root and has no siblings then it is a one node tree. For this we’ll just assign the value of that node to null.

If the target node is not the root and only has one direct sibling, then we want to check if the target node is a left or right sibling of its parent. If it is the left sibling, we want to assign the target’s left sibling as the parent’s left sibling if the target has a left sibling. If the target does not have a left sibling but has a right sibling, we assign that as the parent’s left sibling. If the target is a right sibling to its parent, we do the same for the right side. If there are no siblings it will just assign the value to null.

After all of our “target found” conditionals, we want to have a “break” statement to end the while loop. At the end of the function we want to return “this” which will be our new tree with the target node deleted.

Here is the complete final solution.