Binary search tree–insertion

“ As it is little bit tricky to understand binary search tree.. we will see one by one.. further moving. The insertion is little bit simple, since we need to just find the sub tree where the new number will fit in on a already existing BST”

Introduction

   Binary search tree matches the insertion philosophy of the heap. Heapify function for a max heap basically adds a data item and makes the heap to follow the max heap property by up bubbling. It always assumes the given heap is already a max heap.

  The same assumption we make in a binary search tree as well. We assume the already given tree is a BST and traverse it to find the correct spot

Concept

   Insertion is simple. Just insert the data at the right or left of a sub tree based on the parent node. Even if the parent has no child, the comparison is made to put the element at right spot. Unlike heap, where we compare left and root to insert the right node, here we can directly insert without much confusion.

Heap: both left and right much be less than the root node

BST: left < root < right

This is the important difference to be understood.

Code

BST* createBSTNode(int data)

{

    BST* newNode = new BST();

    newNode->data = data;

    newNode->left = NULL;

    newNode->right = NULL;

    newNode->parent = NULL;

    return newNode;

}

void bst_insert(BST*& tree, BST* node)

{

    BST* prev = NULL;

    BST* iter=tree;

    while(iter != NULL)

    {

        prev = iter;

        if(node->data < iter->data)

            iter = iter->left;

        else

            iter = iter->right;

    }

    // found node is parent to our node

    node->parent = prev;

    // if prev is NULL

    // then this is the first node

    // change the root NODE

    if(prev == NULL)

        tree = node;

    else {

        // now we need to decide where the node

        // should go: left or right

        if(node->data < prev->data)

            prev->left = node;

        else

            prev->right = node;

    }

}

BST* convert_array_bst(int* arr, int size)

{

    BST* tree=NULL;

    for(int i=0;i<size;i++) {

        bst_insert(tree, createBSTNode(arr[i]));

    }

    return tree;

}

void main()

{

    int A[]={6,2,3,9,1,3,6,2,4};

    BST* sort = convert_array_bst(A, 9);

}

Important notes:

• I simply didn’t understand the need for prev. :) Dummies brain.. prev is important to track the previous node while you are iterating.
• If its a binary tree, we only think about left & right nodes. But in a BST, we have a parent node for easy traversal.
• The input array gets sorted automatically when inserted into BST