Binary Search Tree implementation using C

Binary Search Tree is a Binary Tree in which for each node, value of all the nodes in the left subtree is lesser or equal and values of all the nodes in right subtree is greater.

Below is the implementation of Binary Search Tree using Linked List in C. This code allows to

• Insert a new element

• Search for an element

• Find the height of the tree

• Find the minimum element in the tree

• Find the maximum element in the tree

• Pre-Order Traversal

• In-Order Traversal

• Post-Order Traversal

• Level-Order Traversal

• Delete an element

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

#define MAX(x,y) ((x) > (y) ? (x) : (y))

typedef struct Node {
  int data;
  struct Node *left;
  struct Node *right;
} BSTNode;

/*
##############################################################
QUEUE implementation required for Level Order Traversal
##############################################################
*/

typedef struct QNode {
  BSTNode* data;
  struct QNode *next;
} QueueNode;

typedef struct QueueStruct {
  int size;
  struct QNode *head;
  struct QNode *tail;
} Queue;

Queue *initQueue() {
  Queue *q = (Queue *) malloc(sizeof(Queue));
  q->size = 0;
  q->head = NULL;
  q->tail = NULL;
  return q;
}

int isEmpty(Queue *q) {
  return (q->size == 0);
}

void enqueue(Queue *q, BSTNode* value) {
  QueueNode *node = (QueueNode *) malloc(sizeof(QueueNode));
  node->data = value;
  node->next = NULL;
  if (q->size == 0) {
    q->head = node;
    q->tail = node;
  } else {
    q->tail->next = node;
    q->tail = node;
  }
  q->size++;
}

BSTNode* dequeue(Queue *q) {
  BSTNode* returnData = q->head->data;
  if (q->size == 1) {
    q->head = NULL;
    q->tail = NULL;
  } else {
    q->head = q->head->next;
  }
  q->size--;
  return returnData;
}

/* ##############################################################  */

// To create a new Node while inserting new elements

BSTNode *createNewNode(int value) {
  BSTNode *newNode = (BSTNode *) malloc(sizeof(BSTNode));
  if (newNode == NULL) {
    fprintf(stderr, "Error creating new node, terminating program \n ");
    exit(1);
  }
  newNode->data = value;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}

// To insert a new Node in a Binary Search Tree

BSTNode *insertNode(BSTNode *rootPtr, int value) {
  // Empty Tree
  if (rootPtr == NULL) {
    rootPtr = createNewNode(value);
  }
  // Value to be inserted in left-subtree
  else if (value <= rootPtr->data) {
    rootPtr->left = insertNode(rootPtr->left, value);
  }
  // Value to be inserted in right-subtree
  else {
    rootPtr->right = insertNode(rootPtr->right, value);
  }
  return rootPtr;
}

// To search a  Node in a Binary Search Tree

int searchNode(BSTNode *rootPtr, int value) {
  if (rootPtr == NULL)
    return 0;
  if (rootPtr->data == value)
    return 1;
  if (value <= rootPtr->data) {
    return searchNode(rootPtr->left, value);
  }
  if (value > rootPtr->data) {
    return searchNode(rootPtr->right, value);
  }
}

// To find the minimum element in a Binary Search Tree
// For this, traverse to as left as possible

int findMinimum(BSTNode *rootPtr) {
  BSTNode *minElementNode;
  if (rootPtr == NULL)
    return -1;
  minElementNode = rootPtr;
  while (minElementNode->left != NULL) {
    minElementNode = minElementNode->left;
  }
  return minElementNode->data;
}

BSTNode *findMinimumNode(BSTNode *rootPtr) {
  BSTNode *minElementNode;
  if (rootPtr == NULL)
    return -1;
  minElementNode = rootPtr;
  while (minElementNode->left != NULL) {
    minElementNode = minElementNode->left;
  }
  return minElementNode;
}


// To find the maximum element in a Binary Search Tree
// For this, traverse to as right as possible

int findMaximum(BSTNode *rootPtr) {
  BSTNode *maxElementNode;
  if (rootPtr == NULL)
    return -1;
  maxElementNode = rootPtr;
  while (maxElementNode->right != NULL) {
    maxElementNode = maxElementNode->right;
  }
  return maxElementNode->data;
}

// To find the Height of a Binary Search Tree

int treeHeight(BSTNode *root) {
  int leftSubtreeHeight, rightSubtreeHeight;
  if (root == NULL)
    return -1;
  leftSubtreeHeight = treeHeight(root->left);
  rightSubtreeHeight = treeHeight(root->right);
  return MAX(leftSubtreeHeight,rightSubtreeHeight) + 1;
}

// Pre-Order Traversal (Depth First)
// <root> <left-subtree> <right-subtree>

void preOrderTraversal(BSTNode *rootPtr) {
  if (rootPtr == NULL)
    return;
  printf("%d ",rootPtr->data);
  preOrderTraversal(rootPtr->left);
  preOrderTraversal(rootPtr->right);
}

// In-Order Traversal (Depth First)
// <left-subtree> <root> <right-subtree>

void inOrderTraversal(BSTNode *rootPtr) {
  if (rootPtr == NULL)
    return;
  inOrderTraversal(rootPtr->left);
  printf("%d ",rootPtr->data);
  inOrderTraversal(rootPtr->right);
}

// Post-Order Traversal (Depth First)
// <left-subtree> <right-subtree> <root>

void postOrderTraversal(BSTNode *rootPtr) {
  if (rootPtr == NULL)
    return;
  postOrderTraversal(rootPtr->left);
  postOrderTraversal(rootPtr->right);
  printf("%d ",rootPtr->data);
}

// Breadth First Traversal

void levelOrderTraversal(BSTNode *rootPtr) {
  if (rootPtr == NULL)
    return;
  Queue *q = initQueue();
  enqueue(q,rootPtr);
  while(!isEmpty(q)) {
    BSTNode *node = dequeue(q);
    printf("%d ",node->data);
    if (node->left != NULL )
      enqueue(q,node->left);
    if (node->right != NULL )
      enqueue(q,node->right);
  }
}

// Delete a Node from tree

BSTNode *deleteNode(BSTNode *rootPtr, int data) {
  if (rootPtr == NULL)
    return NULL;
  else if (data < rootPtr->data)
    rootPtr->left = deleteNode(rootPtr->left, data);
  else if (data > rootPtr->data)
    rootPtr->right = deleteNode(rootPtr->right, data);
  else {
    // Case 1: No Child, just remove the node and its reference
    if ((rootPtr->left==NULL) && (rootPtr->right==NULL)) {
      free(rootPtr);
      rootPtr = NULL;
    }
    // Case 2 : One Child - either left or right subtree
    else if (rootPtr->left==NULL) {
      BSTNode *temp = rootPtr;
      rootPtr = rootPtr->right;
      free(temp);
    }
    else if (rootPtr->right==NULL) {
      BSTNode *temp = rootPtr;
      rootPtr = rootPtr->left;
      free(temp);
    }
    // Case 3 : Node has two children
    // Find the minimum in right-subtree, copy it's value to targeted node and
    // delete the minimum node from right subtree
    else {
      BSTNode *temp = findMinimumNode(rootPtr->right);
      rootPtr->data = temp->data;
      rootPtr->right = deleteNode(rootPtr->right,temp->data);
    }
  }
  return rootPtr;
}


int main() {
  BSTNode *root;
  root = NULL;
  int c;
  int v, r, nargs;

  while (1) {
    do {
      printf("\n\n######################\n");
      printf("1. Insert the value\n");
      printf("2. Search the value\n");
      printf("3. Find the minimum element in tree\n");
      printf("4. Find the maximum element in tree\n");
      printf("5. Find the height of the tree\n");
      printf("6. Display the tree (Pre Order Traversal)\n");
      printf("7. Display the tree (In Order Traversal)\n");
      printf("8. Display the tree (Post Order Traversal)\n");
      printf("9. Display the tree (Level Order Traversal)\n");
      printf("10. Delete the node from tree\n");
      printf("11. Exit the program\n");
      printf("######################\n");
      printf("Enter the command:");
      nargs = scanf(" %d", &c);
    } while (nargs != 1);

    switch (c) {
    case 1:
      do {
        printf("Enter the value to be inserted:");
        nargs = scanf("%d", &v);
      } while (nargs != 1);
      root = insertNode(root, v);
      break;
    case 2:
      do {
        printf("Enter the value to be searched:");
        nargs = scanf("%d", &v);
      } while (nargs != 1);
      r = searchNode(root, v);
      if (r == 1)
        printf("Element %d found in the tree\n", v);
      else
        printf("Element %d is not found in the tree\n", v);
      break;
    case 3:
      r = findMinimum(root);
      if (r == -1)
        printf("Tree is empty\n");
      else
        printf("Minimum Element in the tree is %d\n", r);
      break;
    case 4:
      r = findMaximum(root);
      if (r == -1)
        printf("Tree is empty\n");
      else
        printf("Maximum Element in the tree is %d\n", r);
      break;
    case 5:
      r = treeHeight(root);
      printf("Height of the tree is %d\n", r);
      break;
    case 6:
      preOrderTraversal(root);
      break;
    case 7:
      inOrderTraversal(root);
      break;
    case 8:
      postOrderTraversal(root);
      break;
    case 9:
      levelOrderTraversal(root);
      break;
    case 10:
      do {
           printf("Enter the value to be searched:");
           nargs = scanf("%d", &v);
         } while (nargs != 1);
      root = deleteNode(root, v);
      break;
    case 11:
      return 0;
      break;
    default:
      printf("Invalid command entered\n");
    }
  }
}