Create a Binary Search Tree from an array

Lets discuss how to create a BST From an array.

Binary Search Tree

Tree’s node structure is as follows,

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

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.

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

Lets create the insert function,

[showads ad=inside_post]

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.

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);
}

Lets see how to use the above code,

    int arr[] = {10,5,15,5,6,7,8,89};
    node * pRoot = getBST(arr, sizeof(arr)/sizeof(int));
    inOrderTraversal(pRoot);

Complete executable code is as follows,

[code language=”css” collapse=”true”]
#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;
}

[/code]

Leave a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Scroll to Top