Basic Operations of BST

The following are the basic operations of Binary Search Tree:

• Insert – It inserts an element in a tree / Create a tree.
• Search – It searches an element in a tree.
• Preorder traversal – Traverses a tree in a pre-order manner.
• Postorder traversal – Traverses a tree in a post-order manner.
• Inorder traversal – Traverses a tree in an in-order manner.

//To insert an element to the tree / create a tree.
void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //Check if tree is empty, create root node
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent  = NULL;

      while(1) {
         parent = current;

         //Go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;

            //Insert an element to the left
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }

         //Go to right of the tree
         else {
            current = current->rightChild;

            //Insert an element to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }
   }
}

//To search a given element in the binary tree
struct node* search(int data) {
   struct node *current = root;
   printf("Visiting elements: ");

   while(current->data != data) {
      if(current != NULL)
      printf("%d ",current->data); 
      
      //if the given number is less than the current element,
      //then go to left subtree

      if(current->data > data) {
         current = current->leftChild;
      }
      //else go to right subtree
      else {                
         current = current->rightChild;
      }

      //The given number is not found on the binary tree.
      if(current == NULL) {
         return NULL;
      }

      return current;
   }  
}