What is BST in C++?

Do you know what is BST in C++? Have you ever thought what is the way to implement BST in C++? Let’s have an experience, of how we can implement BST in C++.

But before we start a discussion about BST in C++, let’s think about its background & its working in simple terms.

For that purpose, we need to assume one scenario:

Suppose, you & your friend are playing Hind & Seck. You both love to play this game. And every time you choose to play this game only.

Now, you & your friend play this game in different locations it may be the ground, it may be your house. Or maybe you all are playing at your friend’s house. Now as you both are playing this game you know the places well to hide for a long time.

Suppose, it is your turn to find out your friend. So, what will you do? Depending upon the location of the game, you know some probable places where your friend can hide. Among those places, you will find out the most suitable one.

If you find your friend there, you win the match. If not, you move to the second most probable place. The places where your friend can hide.

BST in C++ works in the same manner. Depending upon the properties, it performs certain operations. If it correctly follows the properties, then it completes the operation.

But before we start the BST in C++, we need to find What is Binary Tree first.

What Is Binary Tree? Properties of Binary Tree

Data Structures are mainly two types. One is the Linear & another is the Non-Linear. The Tree is a type of Non-Linear Data Structure. The Tree consists of Root Nodes & Leaf Nodes. The uppermost node is known as the Root Node. And the lower nodes are known as the Leaf Nodes. Also, Trees can be further divided into subtrees.

Binary Tree has some unique properties. Let’s make a list of those properties:

1. Every Node in the Binary Tree can only have a maximum of two Leaf nodes or Child Nodes. Any Tree having more than two Child Nodes, can’t be considered a Binary Tree.
2. The Node values of the Left Subtree of the Main Tree should always be lesser than the Root Node value.
3. The Node values of the Right Subtree of the Main Tree should always be greater than the Root Node value.

What Is BST In Data Structure? Read More

Before we start ‘what is BST in Data Structure’, we first need to clarify what commonly a BST called & what is its full form.

BST stands for the Binary Search Tree. As the name suggests it is one type of Binary Tree. And it is an important fundamental type in Data Structure. BST in C++ highly follows the properties of the Binary Tree.

BST not only looks for the immediate child of any subtree. But also, it looks for the child of the child node. This means in a BST, all the nodes of the Left Subtree should be less than the root node. The right side of the Left Subtree should also have a lesser node than the Root node. But it should have a greater node value than the Left Subtree Root Node value.

Is it appearing difficult? Let’s try to know more wisely using the below image.

Here, in the above image, the left-sided image is a correct BST. But the right-sided tree is not in the correct manner. Why does it so? Let’s know it.

We can see a subtree there where the Root Node is 3. It has 1 as Left Child & 6 as Right Child. In this particular subtree, the problem arises. According to the rule, BST will have a greater numbered node all on the Right Side. But we can see that the left side of the subtree which has the Root Node as 6, has 2 as their Left Child.

The number 2 is not applicable there. There the number is applicable which is greater than 3 but less than 6. As we can see in the image which is on the left-hand side. There instead of 3, we have used 4 as node value. Hence, it is a correct representation of BST.

How to do Implementation of BST ? 

BST in C++ has some unique implementation processes. Here we first need to have the nodes of the Tree in Array format. Then we consider the first or last number as the root of the Main Tree. Then depending upon the number, we have to define the BST. The methods go in the following way:

1. Consider the first number as Root Node.
2. Check the next number.
3. If the number is lesser or equal to the value of the Root, then it will be on the Left Side of the Tree.
4. If the number is greater or equal to the value of the Root, then it will be on the Right Side of the Tree.

Suppose, we have given an Array as {3,2,1,7}. Now as per the rule, we will consider the 3 as the Root value. As the next number 2 is less than the value 3, it will be on the left side of the Tree. And as the 1 number is less than both the numbers 3 & 2, so it will be the left child of 2. Then as the number 7 is highest than all. So it will be the Right Child of the Main Tree.

Implementation of BST In C++:

For implementing BST in C++, we need to first develop one structure for Node. The Node will have the fields like the Value, Addresses of Left & Right Node, etc. A common Linked List Type node we have to implement first.

• Main Function: Here, we first take the number of the Nodes as the Array input. There we will act the first number as the Root Node of the Main Tree. Then we will call the BST function to make a BST tree using the rules. Also, after that, we will print that Tree in Preorder form.

int main(){

            // Assigning The Array.

            int arr[] ={3,2,1,7,9};

            int len = sizeof(arr)/sizeof(int);

            // Function Calling

            Node *root = sortedBST(arr,0,len-1); 

            // Printing The Data In Preorder

            preorder(root);

            return 0;}

• Function to Create BST: Here, we will divide the array by finding the middle term of the Array. It is kind of the Quick Sort type process. In this way, we can check every element of the Array. And according to the number related to the Root value, we have to put it into the proper position.

// Function To Implement BST

Node* sortedBST(int arr[],int start , int end)

{

            if(start>end)

             return NULL;

            //  Assigning The Mid Value

            int mid = (start+end)/2;

            // Assigning The Mid Value As Root Node

            Node* root = new Node(arr[mid]);

            // Construct Left & Right Subtree

            root->left = sortedBST(arr, start, mid-1);

            root->right = sortedBST(arr, mid+1  , end);

            return root;

}

Above are the code snippets. If needed, you can go through the full source code provided here. The probable output to build BST in C++ will be the following.

Output:

Conclusion:

As we saw, BST in C++ is very important.

We should clear the basics of recursion & function calling for implementing BST in C++.

We should clear the What Is BST in Data Structures. As well as we need to clear the basics. That is very important while implementing BST in C++.

So, hope you have liked this piece of article. Share your thoughts in the comments section and let us know if we can improve more.

Also, if you guys are looking to get help with C++ Programming Assignments then you can use our C ++ Programming Homework Help Services.

Codingzap also offers a wide range of programming and coding help services for you to benefit from. Don’t miss out! Visit https://codingzap.com/ and our expert team will be there to help you out.