Binary Search Tree C++

BST is a data structure that maintains the data in a sorted list. It is known as a binary search tree because, in the tree, every node has a two children maximum that cannot be increased further. This is known as a search tree because it is used to search or find any item present. We will implement this phenomenon in the C language.

Implementation

In an implementation, the first step is to use a structure for initializing the integer type key and both left and right side nodes. These nodes are defined by using a variable pointer, as they both save the addresses of the alternative nodes. After that, we close the structure.

<img alt="" data-lazy- data-lazy-src="https://kirelos.com/wp-content/uploads/2022/04/echo/image4-11.png" data-lazy- height="272" src="data:image/svg xml,” width=”594″>

We will create a new node again through a structure. The parameter of the function will contain the data that we want to enter in the node.

struct node *newNode (int item)

It will create a new node temp that will store data in it, and the size of the memory will be allocated through malloc(). We will add the item value in the key part of the node. Whereas the left and right parts, which are declared previously in the structure, are declared as Null now because it is the first node. The temp will be returned.

<img alt="" data-lazy- data-lazy-src="https://kirelos.com/wp-content/uploads/2022/04/echo/image6-10.png" data-lazy- height="243" src="data:image/svg xml,” width=”317″>

A function with the name “inorder” is created, and it will accept the root node in the parameter. As we know, the tree contains three main parts: node, left, and right sides of the tree. We will use an if-statement to check if the root is not null. Then, call the function and send the left part of the root. This will display the root itself with an arrow that will denote the direction of the path in the tree. Next, for traversing right, call the inorder function with the right of the root as the parameter.

Inorder(root -> left)

This is how the inorder traversing is done. To insert a new node in the tree, we will use a function that will take a node and the key as parameter values. If the tree is already empty, the new node will be returned. In the second case, if the tree is not empty, then first go to the right side and insert a new node here. For insertion, we will use an if-else statement to check the order for the key. The new key will be going to the left side for the ascending order. If the part that will check the new key is less than the value present in the node already, then enter the key to the left part of the node.

Node – > left = insert (node ->left, key)

Whereas if the key is greater, it will go to the right part.

<img alt="" data-lazy- data-lazy-src="https://kirelos.com/wp-content/uploads/2022/04/echo/image5-11.png" data-lazy- height="435" src="data:image/svg xml,” width=”478″>

After the insertion of the node, we will check the next node or the node that is the successor. A function of min value is created that will create a new node with a name *current. This node will be assigned by a value passed as an argument to the function. It will first find the corner node or the left mode leaf on the left side of the tree. We use a while loop that iterates until the node’s traversing is finished. In other words, the left part of the current node is not null.

Current   =current – >left

Keep assigning the current node the next current’s value inside the loop at the left.

Our tree is traversed and organized by adding leaves on both sides. Each value will be inserted through the function call made from the main program. Now, we need to search for any element and will delete it once it is found.

The tree in C works on the same phenomenon as the linked list does. We will apply the binary search on the tree and perform a delete operation to delete one node or leaf from the tree. A function of the delete node is created; it will contain the tree and the value as parameters. We will check first that the trees must have values inside them. So, the if-statement will be used, and if the root is NULL, it means to return the root only.

<img alt="" data-lazy- data-lazy-src="https://kirelos.com/wp-content/uploads/2022/04/echo/image7-8-e1649586344181.png" data-lazy- height="188" src="data:image/svg xml,” width=”506″>

If (key key)

The key you want to delete is smaller than the root node. Then move to the left side and call the delete function with the left part of the tree, and the key to be deleted.

Root -> left = deletenode ( root ->left, key);

And same goes for the else-if part. If the key is greater than the node key, then go to the right path, call the delete function. Pass the right portion of the tree and the key so that it becomes easy to find the node that you want to delete.

<img alt="" data-lazy- data-lazy-src="https://kirelos.com/wp-content/uploads/2022/04/echo/image7-9-e1649586317952.png" data-lazy- height="207" src="data:image/svg xml,” width=”506″>

Now, coming toward the else part, that is applicable if the node is alone, has no leaf further, or has only a single child ahead. Inside the else part again, if a statement will be used that will check if there is no node on the right side, then add the value on the right side of the node to the new temp node, similarly for the left side.

Struct node * temp = root ->left;

In that condition, free the root. This will remove the value from the root.

Free (root);

<img alt="" data-lazy- data-lazy-src="https://kirelos.com/wp-content/uploads/2022/04/echo/image2-13.png" data-lazy- height="207" src="data:image/svg xml,” width=”665″>

If any node contains two leaves with it, then to search the value, we will use the min value function, and the right part will be sent to the function.

Minvaluenode (root -> right);

When the value to be deleted is found, we will declare it the last part of the tree so that it can be deleted easily.

Root -> key = temp ->key;

After doing this, delete the node,

Root ->right =  delete node (node – >right, temp -> key);

After closing the function, we will declare the main program here. The root node will be set as NULL initially. Using the insert() function call, we will use the root and the number data to the node.

Insert (root, 5);

<img alt="" data-lazy- data-lazy-src="https://kirelos.com/wp-content/uploads/2022/04/echo/image1-15.png" data-lazy- height="323" src="data:image/svg xml,” width=”357″>

The inorder function is called for the traversal of the tree.

Inorder(root);

Then, to delete the node, we will call the delete function.

Root = deleteNode (root, 10);

After the deletion, the values are again displayed.

After writing the code, we will execute it in the terminal of Ubuntu through the compiler.

<img alt="" data-lazy- data-lazy-src="https://kirelos.com/wp-content/uploads/2022/04/echo/image3-12.png" data-lazy- height="109" src="data:image/svg xml,” width=”717″>

As you can see, the seven items are entered into the node. One is deleted, and the rest will be displayed in the same order as before.

Conclusion

A binary search tree is used to store the values in the sorted form. To search any number, all the numbers must be sorted first in order. After that, the specified number is searched by dividing the tree into two parts, making subtrees. The BST implementation is done in the Ubuntu system by explaining an example in an elaborated way. We hope you found this article helpful. Check the other Linux Hint articles for more tips and tutorials.