Lets discuss how to create a BST From an array.

Binary Search Tree

Tree’s node structure is as follows,

Now create a getBST function that accepts an integer pointer and size of array.
Inside this function it creates a pointer to root node and points it to NULL.
Then traverses through all of the array elements and calls the insert function on each of them with root node pointer and current element as parameters. This insert function inserts the element in BST.

Lets create the insert function,

Insert function accepts a pointer to a node pointer and value to be inserted in BST.
It first checks that if passed node pointer is NULL then assigns the new node to passed pointer.
But if the passed pointer is not NULL then it compares the new value with the value of root node.
If it’s value is less than or equal to root node’s value the in will recursively call the insert function on left child of root node else it will recursively call the insert function on right child of root node.

Lets see how to use the above code,

Complete executable code is as follows,

#include<iostream>

typedef struct node
{
    int value;
    node * pLeft;
    node * pRight;
    node(int val = 0)
    {
        value = val;
        pRight = NULL;
        pLeft = NULL;
    }
}node;

void insert(node ** pRoot, int val)
{
    if(*pRoot == NULL)
        *pRoot = new node(val);
    else if((*pRoot)->value <= val)
        insert(&((*pRoot)->pRight), val);
    else if((*pRoot)->value > val)
        insert(&((*pRoot)->pLeft), val);
}

node * getBST(int * arr, int size)
{
    node * pRoot = NULL;
    for(int i = 0; i < size; i++)
        insert(&pRoot, arr[i]);
    return pRoot;
}

void inOrderTraversal(node * pRoot)
{
    if(pRoot && pRoot->pLeft)
        inOrderTraversal(pRoot->pLeft);
    if(pRoot)
        std::cout<<pRoot->value<<" , ";
    if(pRoot && pRoot->pRight)
        inOrderTraversal(pRoot->pRight);

}
int main()
{
    int arr[] = {10,5,15,5,6,7,8,89};
    node * pRoot = getBST(arr, sizeof(arr)/sizeof(int));
    inOrderTraversal(pRoot);
    std::cout<<std::endl;
    return 0;
}

Click Here to Subscribe for more Articles / Tutorials like this.