BST Operations: Insert, Search, Delete - Recursive and Iterative

Write functions in C for following BST operations

1.  Search-both iterative and recursive

2. INSERT_BST- both iterative & recursive

3. DELETE_BST

Recursive:

http://quiz.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/
http://quiz.geeksforgeeks.org/binary-search-tree-set-2-delete/
http://quiz.geeksforgeeks.org/data-structure/binary-search-trees/

Iterative:

void Search_BST_Iterative(int item,struct node *root,struct node *&par,struct node *&loc)
{
struct node *ptr,*ptrsave;
       if(root==NULL) //Tree EMPTY
         {  loc=NULL;
            par=NULL;
            return;
         }
       if(item==root->data) //Item is at root
         {  loc=root;
            par=NULL;
            return;
         }
       //Initialise ptr & ptrsave
        
         if(item<root->data)
                 ptr=root->left;
         else
                 ptr=root->right;
         ptrsave=root;

         while(ptr!=NULL)
         {   
            if(item==ptr->data)
              {   loc=ptr;
                  par=ptrsave;
                   return;
              }
            ptrsave=ptr;
            if(item<ptr->data)
                ptr=ptr->left;
            else
                ptr=ptr->right;
         }
loc=NULL; //ITEM NOT FOUND
par=ptrsave;
}

Insert_BST_Iterative:

void INSERT_BST_Iterative(struct node *&root,int item)
{struct node *tmp,*parent,*location;
tmp=(struct node*)malloc(sizeof(struct node));
tmp->data=item;
tmp->left=NULL;
tmp->right=NULL;
Search_BST_Iterative(item,root,parent,location);
if(location!=NULL)
    {printf("Data already present");
     return;
    }
if(parent==NULL)
    root=tmp;
else
    if(item<parent->data)
        parent->left=tmp;
    else
        parent->right=tmp;
}

Runtimes:

Both the BST search and insert algorithms share the same running time: log₂ n in the best case, and linear in the worst case. The insert algorithm's running time mimics the search's because it essentially uses the same tactics used by the search algorithm to find the location for the newly inserted node.

While binary search trees ideally exhibit sub-linear running times for insertions, searches, and deletions, the running time is dependent upon the BST's topology. The topology, as we discussed in the Inserting Nodes into a BST section, is dependent upon the order with which the data is added to the BST. Data being entered that is ordered or near-ordered will cause the BST's topology to resemble a long, thin tree, rather than a short, wide one. In many real-world scenarios, data is naturally in an ordered or near-ordered state.

The problem with BSTs is that they can become easily unbalanced. A balanced binary tree is one that exhibits a good ratio of breadth to depth. As we will examine in the next part of this article series, there are a special class of BSTs that are self-balancing. That is, as new nodes are added or existing nodes are deleted, these BSTs automatically adjust their topology to maintain an optimal balance. With an ideal balance, the running time for insertion, searches, and deletion, even in the worst case, is log₂ n. 

Delete BST Iterative:

void case_a(struct node *&root,struct node *par,struct node *loc)
{    if(par==NULL)
        root=NULL;
    else
        if(loc==par->left)
            par->left=NULL;
        else
            par->right=NULL;
}

void case_b(struct node *&root,struct node *par,struct node *loc)
{struct node *child;
//Initialaise CHILD
if(loc->left!=NULL)
    child=loc->left;
else
    child=loc->right;
if(par==NULL)
    root=child;
else
    if(loc==par->left)
        par->left=child;
    else
        par->right=child;
}   

void case_c(struct node *&root,struct node *&par,struct node *&loc)
{
     struct node *ptr,*ptrsave,*suc,*parsuc;
     ptrsave=loc;
     ptr=loc->right;
    while(ptr->left!=NULL)
    {    ptrsave=ptr;
        ptr=ptr->left;
    }
suc=ptr;
parsuc=ptrsave;

if(suc->left==NULL && suc->right==NULL)
                   case_a(root,parsuc,suc);
else
                   case_b(root,parsuc,suc);

if(par==NULL)
    root=suc;
else
    if(loc==par->left)
        par->left=suc;
    else
        par->right=suc;
   
    suc->left=loc->left;
    suc->right=loc->right;
}      

void DELETE_BST_Iterative(struct node *& root,int data)
{struct node *parent,*location;
 if(root==NULL)
{printf("Tree Empty");
 return;}Search_BST_Iterative(data,root,parent,location);
if(location==NULL)
{printf("DATA Not Present in Tree");
 return;}

if(location->left==NULL && location->right==NULL)
    case_a(root,parent,location);
if(location->left!=NULL && location->right==NULL)
    case_b(root,parent,location);
if(location->left==NULL && location->right!=NULL)
    case_b(root,parent,location);
if(location->left!=NULL && location->right!=NULL)
    case_c(root,parent,location);
free(location);
}

Useful Links on BST:
Java Version:
http://algorithms.tutorialhorizon.com/binary-search-tree-complete-implementation/

http://msdn.microsoft.com/en-us/library/aa289150(v=vs.71).aspx