It’s been a long time since I was first introduced to binary trees. Back in college, I don’t remember if we actually tackled the problem, if I tackled it or if I just took a sample solution from google. Never the less, recently I was intrigued to find out exactly how deleting a node from a binary search tree works. It has always confused the heck out of me.

So… this past week I decided to tackle it head-on. Because… why not… I love programming. It’s like puzzle solving to and I don’t like to leave unresolved knowledge on the table. Below is my description of the steps of how the deletion works. If you rather jump right to the code, you can do so at https://github.com/fernandozamoraj/js_sandbox

A quick refresher for those of you not familiar with binary trees. A binary search tree is composed of nodes. The entry point to the tree is known as the root node. Each node has two pointers to two other nodes (aka left and right) as wells as a data property. Each pointer can be either null or point to another node that follows the same rules. The power of the binary search tree is that it is very fast for performing searches because you essentially divide and conquer to find the node you are looking for.

A node in C# would look like below. It’s easier to describe it in a classy way, so I use C# instead of JavaScript.

//Ignore the bad practices of 0 encapsulation... //for demonstration purposes //We could use C# properties but not all languages have properties. //Therefore it is easier for readers from other languages to understand this. public class Node{ public int Data; public Node Left; public Node Right; public Node(int val){ Data = val; left = right = null; } }

Below is an example of a binary search tree (BST). This BST is perfectly balance but a BST does not have to meet a perfectly balanced requirement so long as it follows the rule of smaller to the left and larger to the right.

*Figure 1. A binary search tree (BST). It also happens to be perfectly balanced.*

Notice that in a BST each node has smaller children than itself to its left and larger children (or same size) to its right. When deleting nodes the tree must maintain the rule of this structure. Violating this rule will make the tree lose the power of searching.

Maintaining this structure of this rule allows you to navigate a search very easily. If the value you are searching for is smaller than the current node you navigate to the left. If it’s larger you navigate to the right. If it’s the same then you have found the node you are looking for.

Inserting nodes is rather easy as well. You simply navigate the tree as you would the search and once you find the null pointer where the new node belongs you attach your node there.

## Deleting A Node

Deleting a node is one of the hardest things or most complex things you can do in data structures. I’m not sure if there is a harder one.

There are several reasons why this is so. First, it’s very difficult to keep track of the nodes because there are so many steps. Second, it’s really difficult to visualize all the cases in your head. So before we dig into code let’s examine this visually.

## Determining All the Delete Cases

When you tackle a problem, it is easier to first determine all the different cases so that the solution solves all possible scenarios.

In the quest for understanding deletion, I came up with my own set of cases. These may differ from way-more respectable figures in the algorithms and data structures world. These cases are mostly for me, but you are welcome to use them to aid you in your quest for understanding this problem.

## Case 1 – Attempting to Delete a Node That is Not Part of the Tree

The first case is when the node you are targeting does not exist in the tree. This is a very easy case to handle since the binary search tree is optimal for finding what your are looking for. In this case, you simply search the tree and don’t delete anything.

## Case 2: Deleting a Leaf Node

The second case is to delete a leaf node. A leaf node is one that has no left and no right child. This case is easy as well. You simply disconnect the node’s parent pointer to it.

*Figure 2. Deleting a leaf node. Notice the parent (2) simply deletes the connection to the target node (3).*

In the code example, I decided to use Javascript. Typically, you will find yourself having to do this in C or C++ or maybe even Java. The reason I chose Javascript is that it’s easier to demonstrate with and it’s a lot faster for me to code in.

The approach that I took was to avoid an Object Oriented approach. Instead, I took a procedural approach. The main difference between this Javascript example and something like C would be that you must free the memory allocated to the target node, but otherwise, it would be very easy to convert the code over to C. It wouldn’t be much more difficult to convert it to C++ if you have a good grasp on OOP.

## Cases 3 and 4 – Delete a Node With Exactly One Child

I decided to combine cases three and four because they operate almost exactly the same way. They are still separate because they are two different conditions. The condition is when the target node has only either a left or a right child exclusively.

Let’s call case 3 the case where the target node has a left child but no right child. In this case, you can simply promote the left child up to the position of the parent. To do this you must simply take the target’s node parent and point the left pointer to same node of the left pointer of the target node.

**Note: the black connectors determine the left and right pointers to nodes. The red curved arrows indicate the new connection from node. The X’s indicate the connect will be severed as part of the operation.*

*Figure 3. Deleting a node that has a left child and no right child. Notice that 1 gets promoted into the target node’s (3) position*

Case 4 is the same but the target node has right child but no left child. This time it’s the right child subtree that gets promoted.

That case is also very simple to handle. You simply perform the same steps but instead of the left child you do it with the right child.

## Case 5 – Delete a Node That Has a Left and a Right Child

Case 5 is where I found it difficult and I think I am not alone in this struggle. In case 5 the target node has both a left and right child. So who gets promoted? Well, the easiest way to handle this is to take the smallest node of the right side of the target node. It must always be the right side.

Well…. not exactly. You could do the opposite, take the oldest child on the left side and that would work. For my case, I decided to always target the right. Either way will maintain the integrity of the BST.

Case 5 is rather complex, so I decided to break it down further to declutter all the operations. Thus Case 5 has three subcases.

### Case 5.1 – The Right Child Has No Left Child

Case 5.1 Is where the right child of the target has no left child. This is simple. You simply promote right child of the target into the target’s position.

*Figure 4. The successor, in this case, is 7. The successor (7) gets promoted to the target node’s (6) position and it must adopt the target node’s left child subtree (5).*

### Case 5.2 – The Right Child Has A Left Subtree That Ends in a Left Leaf Node

This case is where the right child of the target has a left subtree that leads all the way down to a leaf node. In this case, you simply walk all the way down to the leaf node and promote that node to take the place of the target. You must disconnect the successor from its parent. Then you must connect the left and right child subtrees of the target to the successor.

*Figure 5. In this case, 7 was promoted into the place of the target node (6). The replacement node adopts the left (5) and right (9) child subtrees of the target node. The successor’s parent (8) disconnects or releases its left child (7).*

### Case 5.3 – The Right Child Has A Left Subtree Where the Smallest Left Node Has A Right Child Sub Tree

That’s a mouthful there. This case is similar to case 5.2 but this is where the youngest child (successor 7) has a right child subtree (8). In this case, you are still promoting the youngest child up to take the place of the target. But there is an additional requirement that you must now assign the right child (8) subtree as the left child of the successor’s parent (9).

*Figure 6. In this case, notice that the successor (7) got promoted to the target node’s (6) position but its right child subtree (8) had to be adopted by the successor’s former parent (9).*

In this case, the order of disconnecting the nodes is extremely important.

Step 1: Get a separate pointer to the target node

Step 2: Point the target node’s parent (4) right child to the successor (7).

Step 3: Point the successor’s parent’s (9) left child to the successor’s righ child (8)

Step 4: Assign the target node’s left and right children to the target node’s left and right children respectively.

## Case 6 – Delete the Root Node

Sometimes the target node may turn out to be the root. This can be handled in different ways. In my case, since I broke out all the other cases into separate functions and they all have a dependence on a non-null parent to work correctly, I simply decided to give the root a temporary parent and make the root a right child of that parent.

Once I pointed to the new root I disconnected this parent and continued on.

Some tutorials will not address it as the last case but rather as the first. Regardless, it is something that must be dealt with.

The key thing here is to hold a pointer to the previous root so that you can make any changes and once those changes are made, point the root to the new root.

## Summary

Notice that in all cases you must know the parent. Even though we are deleting the target node, it is the parent that must be modified to no longer point to the node being deleted. In some cases, the children left behind must be adopted by the target node’s parent.

In many cases, the successor has children that cannot be left out orphaned. They must be adopted by the successor’s parent. So in those cases, it is important to track the successor’s parent.

It is very important to perform the steps in a way that prevents you from losing a reference to the nodes that need to be reconnected.

Another factor is that many times you have to figure out which child the succesor is of its parent. Same with the target node. This is pretty easy if you simply compare the values of a parent to the value of the child. A child that has a value lower than its parent is a left child otherwise it is a right child. C might make it easier by comparing actual pointer values, but I’ve not yet tried it sinc I didn’t code this in C.

## “Show Me the Codes”

Now for some code. Sometimes it is still difficult to see all this visually. And this visual does not lay out the order of the steps to disconnect and reconnect all the nodes.

So… to get a better grasp of the steps involved, visit this code and feel free to fork it, copy it, tinker with it.

Feel free to click the raw button, copy the code and run it in JSBin to get a good visual of how it works.

https://github.com/fernandozamoraj/js_sandbox/blob/master/binary_tree.js

Until next time, happy coding.

Oh… and please please leave me a comment. It would mean so much to hear feedback.