bst1

#include<stdio.h>

#include<stdlib.h>

struct node {
  struct node * lchild;
  int info;
  struct node * rchild;
};
typedef struct node * NODE;
NODE temp = NULL, cur = NULL, prev = NULL, root = NULL;

NODE getnode() {
  NODE x;
  x = (struct node * ) malloc(sizeof(struct node));
  x -> lchild = NULL;
  x -> rchild = NULL;
  return x;
}

NODE insert(int item, NODE root) {
  NODE temp, cur, prev;
  temp = getnode();
  temp -> info = item;
  if (root == NULL) {
    root = temp;
    return root;
  } else {
    prev = NULL;
    cur = root;
    while (cur != NULL) {
      prev = cur;
      cur = (temp -> info < cur -> info) ? cur -> lchild : cur -> rchild;
    }
    if (temp -> info < prev -> info)
      prev -> lchild = temp;
    else if (temp -> info > prev -> info)
      prev -> rchild = temp;
  }
  return root;
}
void inorder(NODE ptr1) {
  if (ptr1 != NULL) {
    inorder(ptr1 -> lchild);
    printf("%d\t", ptr1 -> info);
    inorder(ptr1 -> rchild);
  }
}

void preorder(NODE ptr2) {
  if (ptr2 != NULL) {
    printf("%d\t", ptr2 -> info);
    preorder(ptr2 -> lchild);
    preorder(ptr2 -> rchild);
  }

}

void postorder(NODE ptr3) {
  if (ptr3 != NULL) {
    postorder(ptr3 -> lchild);
    postorder(ptr3 -> rchild);
    printf("%d\t", ptr3 -> info);
  }

}

void search(NODE root) {
  int item, found = 0;
  NODE cur;
  printf("enter the element to be searched\n");
  scanf("%d", &item);
  if (root == NULL)
  {
    printf("tree is empty\n");
    return;
  }
  cur = root;
  while (cur != NULL) {
    printf("\nComparing key(%d) : cur(%d)",item,cur->info);
    if (item == cur -> info) {
      printf("\nHere");
      printf("found key %d in tree \n", cur -> info);
      return;
    }
    if (item < cur -> info)
      cur = cur -> lchild;
    else
      cur = cur -> rchild;
  }
    printf("key not found\n");
}
int main() {
  int choice, item, n, i;
  NODE root = NULL;
  while (1) {
    printf("1.create BST of N integers\t 2.BST traversal\n");
    printf("3. binary search\t 4.exit\n");
    printf("enter your choice:");
    scanf("%d", & choice);
    switch (choice) {
    case 1:
      printf("\n enter the nuber of elements:");
      scanf("%d", & n);
      for (i = 0; i < n; i++) {
        printf("enter the item to be inserted\n");
        scanf("%d", &item);
        root = insert(item, root);
      }
      break;
    case 2:
      if (root == NULL)
        printf("\ntree is empty\n");
      else {
        printf("\ninorder traversal");
        inorder(root);
        printf("\n preorder traversal");
        preorder(root);
        printf("\n postorder traversal");
        postorder(root);
      }
      break;
    case 3:
      search(root);
      break;
    case 4:
      exit(0);
      break;
    default:
      printf("invalid choice\n");
      break;
    }
  }
}