C code to implement Binary Search Tree using Father Field

/* C program to implement binary search tree using father field */

#include <stdio.h>

/* Parent field=father field*/
struct st
{
    int data;
    struct st* lc;
    struct st* rc;
    struct st* parent;
};

struct st *root=NULL;
struct st * find_leftmost(struct st *);
struct st * find_succ(struct st *, struct st *);
struct st * insert(struct st *,int);

int main()
{
  struct st* temp, *succ;
  int ch,ele,n,i;
  clrscr();
  while(1)
    {
    printf("\n\t\tMENU\n\t1.To insert\n\t2.For inorder Traversal\n\t0.To exit\n\t");
    scanf("%d",&ch);

        switch(ch)
        {
         case 1:
            printf("\n\tEnter number of elements\n\t");
            scanf("%d",&n);
            printf("\n\tEnter %d numbers to be inserted \n\t: ",n);
            for(i=0;i<n;i++)
            {
            printf("\n\t");
            scanf("%d",&ele);
            root=insert(root,ele);
            }
           break;
         case 2:
         clrscr();
         printf("\n\tInorder traversal using Father field\n\t");
         temp=find_leftmost(root);
         printf("%d ",temp->data);
         a:
         succ=find_succ(root,temp);
         if(succ !=  NULL)
         {
            printf("%d ",succ->data);
            temp=succ;goto a;
         }
        break;
        case 0:
        getch();
        exit(0);
        default:printf("Wrong choice pleas enter valid option  ");
        }
    }
}

/* Creating binary search tree using parent field */

struct st* insert(struct st* root, int ele)
{
    struct st *temp;
    if (root== NULL)
    {
    struct st* root = (struct st*)
    malloc(sizeof(struct st));
    root->data   = ele;
    root->lc   = NULL;
    root->rc  = NULL;
    root->parent = NULL;
    return(root);
    }
  else
  {
    if (ele <= root->data)
    {
     temp = insert(root->lc, ele);
     root->lc  = temp;
     temp->parent= root;
    }
    else
    {
    temp = insert(root->rc, ele);
    root->rc = temp;
    temp->parent = root;
    }
       return root;
  }
}

/* Finding left most node */

struct st * find_leftmost(struct st* node) {
    struct st* current = node;
    while (current->lc != NULL) {
    current = current->lc;
  }
  return current;
}

/* Finding succeeder of the node  */

struct st * find_succ(struct st *root, struct st *n)
{
   struct st *p;
    if( n->rc != NULL )
    return find_leftmost(n->rc);
    p= n->parent;
   while(p != NULL && n == p->rc)
   {
     n = p;
     p = p->parent;
   }
  return p;
}

/* Output of Binary Search Tree using Father Field Program */

Output of BST using Father Field

Output of BST using Father Field

For more related to Data Structure check List of Data Structure Programs. If you like this program, Please share and comment to improve this blog.