Binary search tree operations

Knowing how binary search trees work, let’s study how to work with them. The binary search tree operations that can be performed are:  Searching, insertion and deletion of a node.

Searching a node

When we want to retrieve data from our binary search tree structure, we will take advantage of the fact that these structures are ordered. We would start by checking the root node, and if this is the one we are looking for, we are done. If it is not, we would move to your left or right child, depending on whether the data we are looking for is less or greater than that contained in the parent node. And so we would continue until we find the data or finish touring the tree without finding it.

This process is recursive since when we move to a child node, we can consider it as the root node of a new tree. The search process could be expressed as:

Node search process
Node search process

That we could also represent in pseudocode as follows:

Found (Tree, searched){
If the Tree does not exist -> Not Found
If the Tree existsl {
   If root value=searched ->Found
   If root value <> searched{
       If root value >searched{
           Tree = left node
           Found(Tree, searched)
           }
       If root value < searched{
           Tree = right node
           Found(Tree, searched)
           }
       }
   }
}

Analyzing how to search for data in a binary search tree, we can imagine the tremendous savings compared to searching in a sequentially indexed table.  If we take the example of the providers file with 1,000 providers, the average number of records that we would have to go through in our searches would be 500, while in the binary tree, assuming that it is balanced, at most we will have to go through 10, one per level(0-9).

Inserting a node

To insert a node in a binary search tree, we go through it similarly as we did in the searching process, and when we reach a free “space” we will insert the node there.

The process would be as follows:

Node insertion process
Node insertion process

Delete a node

This is the most complicated of the three binary search tree operations. First of all, to eliminate a node, you have to locate it in the structure of the tree, which we already know how to do, it is the first operation I talked.

Once we have located the node, we will have to act differently to eliminate it depending on the number of children it has. We can find three situations for the node to eliminate:

  • It does not have children, it is a Leaf node: We simply delete the node and put to null the reference that the parent had pointing to that node.
  • It has 1 child: We will make the parent node of the node to delete, point to the only child who has the node to delete and then delete the node.
  • It has 2 children: This is the most complex case. When removing the node, what of its children do we promote to the gap left by the deleted node? Will we promote the right or the left subtree? We have two options:
    1. Select from the left subtree the node that will take the place of the deleted node. Then, we have to look for the node with the highest value of the entire left subtree, which should be the one on the rightmost.
    2. Select from the right subtree the node that will take the place of the deleted node. We have to look for the node with the lowest value of the entire right subtree, which should be the one on the leftmost.

Example of binary search tree operations

In this section, we will see examples of operations with binary search trees. I’m going to use a binary tree with numbers as it’s more intuitive. It is easier to sort, and it’s going to be easier to follow up.

Step 1: The tree

I use a binary tree with integer values on the nodes because I think it is more visual and you can follow the explanation easily. It is easier to sort numbers than names.

Our starting tree would be as follows:

The binary search tree
The binary search tree

Step 2: Finding a node

Let’s imagine that we want to find the node with a value of 24. The path we would travel is the one that is painted in red:

Finding a node
Finding a node

We begin to walk the tree from the root, which is the first node whose value is compared with the value we are looking for. The process has the following steps:

  • We compare the value sought (24) with that of the root node (18). As the value sought is higher, if it exists in the tree, it would be on the path to the right.
  • We move to the right child of the root node. We compare the value sought (24) with the value of the right child node (25), as the first is smaller, if it exists in the tree, it would be in the left subtree.
  • We move to the left child (25), which is node(23).
  • We compare the value sought (24) with the value of the node (23). Since the first is higher, if it exists, it would be on the path to the right.
  • We move to the right child of node(23), which is node(24). We have reached the node sought.

Step 3: Find a node that does not exist

Suppose now that we look for the node of value 27, which we can verify does not exist in our tree. The search process does not change with respect to the one explained in Step 2, however, in this case, we will not find the node, we will reach a gap where the requested node could be, but it is not.

Node not found
Node not found

We begin to walk the tree from the root, which is the first node whose value is compared with the value we are looking for.  The process is the following:

  • We compare the value sought (27) with that of the root node (18). As the value sought is higher, if it exists in the tree, it would be on the path to the right.
  • We move to the right child of the root node. We compare the value sought (27) with the value of the node (25), since the first is higher, if it exists in the tree, it would be in the right subtree.
  • Therefore, we move to the right child of node(25) and find node(29). The value sought (27) is smaller than the value of the node (29), so if the node with value 27 exists, it would be to the left of the node with value 29.
  • We try to move to the left child of node(29) but the corresponding pointer points to null, and then node (29) has no left child.
  • Finally, it is concluded that there is not a node with a value of 27 in this tree

Step 4: Insert a node

Suppose we want to insert the node of value 30 in our tree. The first thing to do is to go through the tree looking for the node that you want to insert, following the search process already explained in the previous steps.

If we find the node with the value we want to insert, we would give an error message indicating that the value already exists, since duplicates are not supported.

On the contrary, if in the search process we reach a free space, we insert the node into that place.

An example of the insertion process for a value that does not exist is shown in the following image. A node with a value of 30 is inserted into the binary search tree. The path followed is marked in red.

Insertion of a node
Insertion of a node

However, if the value we want to insert already exists, when performing the search process we will find it and then we will issue the corresponding error message, indicating that the value already exists and therefore cannot be inserted. In the following image, you can see this situation in case the value to be inserted was 8.

Error inserting a node
Error inserting a node

Step 5: Remove a leaf node

I had said that the process of removing a node is the most complicated and that different strategies can be adopted depending on the number of children the node to be eliminated had.

The simplest case is when the node has no children, that is, when it is a leaf node.

Removing a node
Removing a node

In this case, we simply look for the node and delete it. We also made the father node that pointed at it, point to null.

Step 6: Delete a node with one child

To delete a node that has one child, we first locate it and then make the pointer that points to the node to be deleted, point to the child node of it.

The process is detailed in the following figure:

Deleting a node with one child
Deleting a node with one child
  • We start by locating the node to delete, in this case, the one with the value 12.
  • We compare with the root node, since 12 is less than 18, we move to the left child node.
  • The left child has the value 9, which is less than 12, then we move to the right child of it, and in that node we already find the value we were looking for.
  • The node with value 12, has a single child, the left one, with the value 11.
  • We make the pointer that pointed to the node to delete, located in its parent, point to the child of it. That is, the node with value 9 happens to have a right child with value 11.
  • we can delete node 12.

Step 7: Delete a node with two children, promoting a value from the left subtree

We had seen that when we want to delete a node that has two children, we have two possibilities to fill the gap that this node leaves: We can take the node of its left subtree that has a higher value, or the node of its right subtree that has a lower value.

Let’s look at the first case with the example of the following figure:

Deleting a node and promoting a value from the left subtree
Deleting a node and promoting a value from the left subtree
  • We want to remove the root node, with a value of 18.
  • The root node has two subtrees, the one on the left with a root node with a value of 9, and the one on the right with a root node with a value of 25.
  • By eliminating the node of value 18, we will have to replace it with another node of the tree, which would take its position in the structure. This time, we are going to look for this node in the left subtree.
  • As we look for the node in the left subtree, we have to look for the node with the highest value. Considering the way the tree is built, the node we are looking for would be the one located more to the right in the subtree. In our case, the node of value 12.
  • We replace the node of value 18 with the node of value 12.
  • We delete the initial node of value 12 that we have previously copied to the node of value 18. The initial node with value 12 cannot have two children, because if it had a child on the right, that node would have a value higher than 12 and it would be the highest value of the left subtree. So this node can have a left child or none. Both cases of removing a node have been explained in steps 6 and 5 respectively.

After performing these operations, we are left with the following binary tree:

Binary search tree resulting -> Promoting the left subtree
Binary search tree resulting -> Promoting the left subtree

Step 8: Delete a node with two children, promoting a value from the right subtree

This time, when removing a node with two children, we are going to look in the right subtree, looking for the node with the smallest value.

To analyse how to proceed, we are going to use the same example as in the previous case, but this time we will go through the right subtree, looking for the lowest value.

In the following figure, we can appreciate the process:

Deleting a node and promoting a value from the right subtree
Deleting a node and promoting a value from the right subtree
  • We want to delete the root node, with value 18.
  • We look in the right subtree, the node that contains the lowest value, which will match the one that is further to the left in the right subtree. This node is the node with value 21.
  • We replace the node of value 18 with the node of value 21.
  • We delete the initial node of value 21 that we have previously copied to the node of value 18.

After performing these operations, we are left with the following binary tree:

Binary search tree resulting -> Promoting the right subtree
Binary search tree resulting -> Promoting the right subtree

NOTE:

This post is part of the collection “Data Access and Storage Systems”. You can see the index of this collection here