Binary Search Tree

/* Binary Search Tree */

/* @BEGIN_OF_SOURCE_CODE */

#include <stdio.h>
#include <stdlib.h>

struct tree_node
{
     struct tree_node *left ;
     struct tree_node *right ;
     struct tree_node *parent ;
     int key ;
};

typedef struct tree_node *TREENODEPTR ;

TREENODEPTR bst_search(TREENODEPTR r, int k)
{
     while (r != NULL && k != r->key)
          if (k < r->key)     r = r->left ;
          else r = r->right ;

     return r ;
}

/* 
     r : points to root of the tree
     n : pointer to the new node to be inserted
*/
void bst_insert(TREENODEPTR *r, TREENODEPTR n)
{
     TREENODEPTR p = NULL ;
     TREENODEPTR x = *r ;

     while (x != NULL) {
          p = x ;
          if (n->key < x->key)
               x = x->left ;
          else x = x->right ;
     }

     n->parent = p ;
     if (p == NULL)
          *r = n ;
     else if (n->key < p->key)
          p->left = n ;
     else p->right = n ;
}

void clear(TREENODEPTR r)
{
   if (r==NULL)
      return ;

   if (r->left) clear(t, r->left) ;
   if (r->right) clear(t, r->right) ;

   free(r) ;
}

int main()
{
     int n ;
     TREENODEPTR root, tmp ;

     #ifndef ONLINE_JUDGE
     freopen("bst.in", "r", stdin) ;
     #endif

     root = NULL ;

     while (scanf("%d", &n) != EOF) {
          if ((tmp = bst_search(root, n)) == NULL) {
               tmp = (TREENODEPTR) malloc(sizeof(struct tree_node)) ;
               tmp->key = n ;
               tmp->left = NULL ;
               tmp->right = NULL ;
               tmp->parent = NULL ;
               bst_insert(&root, tmp) ;
          }
          else {
               printf("Element [%d] already exists\n", n) ;
          }
     }

     if (root) {
          clear(root) ;
          free(root) ;
     }

     return 0;
}

/* @END_OF_SOURCE_CODE */