binary search tree in c string code example

Example 1: binary search tree program in c

// Binary Search Tree operations in C

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

struct node {
  int key;
  struct node *left, *right;
};

// Create a node
struct node *newNode(int item) {
  struct node *temp = (struct node *)malloc(sizeof(struct node));
  temp->key = item;
  temp->left = temp->right = NULL;
  return temp;
}

// Inorder Traversal
void inorder(struct node *root) {
  if (root != NULL) {
    // Traverse left
    inorder(root->left);

    // Traverse root
    printf("%d -> ", root->key);

    // Traverse right
    inorder(root->right);
  }
}

// Insert a node
struct node *insert(struct node *node, int key) {
  // Return a new node if the tree is empty
  if (node == NULL) return newNode(key);

  // Traverse to the right place and insert the node
  if (key < node->key)
    node->left = insert(node->left, key);
  else
    node->right = insert(node->right, key);

  return node;
}

// Find the inorder successor
struct node *minValueNode(struct node *node) {
  struct node *current = node;

  // Find the leftmost leaf
  while (current && current->left != NULL)
    current = current->left;

  return current;
}

// Deleting a node
struct node *deleteNode(struct node *root, int key) {
  // Return if the tree is empty
  if (root == NULL) return root;

  // Find the node to be deleted
  if (key < root->key)
    root->left = deleteNode(root->left, key);
  else if (key > root->key)
    root->right = deleteNode(root->right, key);

  else {
    // If the node is with only one child or no child
    if (root->left == NULL) {
      struct node *temp = root->right;
      free(root);
      return temp;
    } else if (root->right == NULL) {
      struct node *temp = root->left;
      free(root);
      return temp;
    }

    // If the node has two children
    struct node *temp = minValueNode(root->right);

    // Place the inorder successor in position of the node to be deleted
    root->key = temp->key;

    // Delete the inorder successor
    root->right = deleteNode(root->right, temp->key);
  }
  return root;
}

// Driver code
int main() {
  struct node *root = NULL;
  root = insert(root, 8);
  root = insert(root, 3);
  root = insert(root, 1);
  root = insert(root, 6);
  root = insert(root, 7);
  root = insert(root, 10);
  root = insert(root, 14);
  root = insert(root, 4);

  printf("Inorder traversal: ");
  inorder(root);

  printf("\nAfter deleting 10\n");
  root = deleteNode(root, 10);
  printf("Inorder traversal: ");
  inorder(root);
}

Example 2: binary search tree program in c

// credit @callmemoeen

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

#define NULL 0

struct treeNode
{
    int data;
    struct treeNode *left;
    struct treeNode *right;
};

typedef struct treeNode TN;

TN *root;

TN *Delete_aux(TN *t, int item);
void print_postorder(TN *t);
void print_inorder(TN *t);
void print_preorder(TN *t);
void Delete(int item);

void init_tree()
{
    root = NULL;
}

TN *createNode(int item)
{
    TN *temp = (TN *)malloc(sizeof(TN));
    temp->data = item;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

void print_tree_aux(TN *t, int depth)
{
    if (t == NULL)
        return;

    print_tree_aux(t->right, depth + 1);
    for (int i = 0; i < depth; i++)
        printf("\t");
    printf("%d---------------------------------\n", t->data);
    print_tree_aux(t->left, depth + 1);
}

void print_tree()
{
    printf("Printing tree ************************************\n");
    print_tree_aux(root, 0);
    printf("Complete ************************************\n");
}

TN *insert_aux(TN *t, int item)
{

    if (t == NULL)
    {
        return createNode(item);
    }

    if (item < t->data)
    {
        t->left = insert_aux(t->left, item);
        return t;
    }
    else
    {
        t->right = insert_aux(t->right, item);
        return t;
    }
}

void insert(int item)
{
    root = insert_aux(root, item);
}

TN *search_aux(TN *t, int key)
{
    if (t == NULL)
        return NULL;
    if (t->data == key)
        return t;
    else if (t->data > key)
        return search_aux(t->left, key);
    else
        return search_aux(t->right, key);
}

TN *search(int key)
{
    return search_aux(root, key);
}

TN *Leftmost(TN *t)
{
    TN *temp = t;
    while (temp->left != NULL)
    {
        temp = temp->left;
    }
    return temp;
}

TN *Delete_aux(TN *t, int item)
{
    TN *temp;
    // check if the tree is empty
    if (t == NULL)
        return NULL;
    // find the node with the arguement value recursively
    if (t->data > item)
    {
        t->left = Delete_aux(t->left, item);
        return t;
    }

    else if (t->data < item)
    {
        t->right = Delete_aux(t->right, item);
        return t;
    }
    else
    {
        // case 1: node with no child deletion
        if (t->left == NULL && t->right == NULL)
        {
            free(t);
            return NULL;
        }

        // case 2: 1 child only deletion. to be deleted node has a child on right branch
        else if (t->left == NULL)
        {
            temp = t->right;
            free(t);
            return temp;
        }
        // case 2: 1 child only deletion. to be deleted node has a child on left branch
        else if (t->right == NULL)
        {
            temp = t->left;
            free(t);
            return temp;
        }
        else
        {
            // get the smallest node in the right subtree temp = Leftmost(t->right)
            t->data = temp->data;
            t->right = Delete_aux(t->right, temp->data);
            return t;
        }
    }
}

void Delete(int item)
{
    TN *temp;
    // search() returns the node that contains the flag value
    temp = search(item);
    Delete_aux(root, item); 
}
void print_preorder(TN *t)
{
    if (t == NULL)
        return;

    printf("%d ", t->data);   // root
    print_preorder(t->left);  // left
    print_preorder(t->right); // right
}

void print_inorder(TN *t)
{
    if (t == NULL)
        return;

    print_inorder(t->left);  // left
    printf("%d ", t->data);  // root
    print_inorder(t->right); // right
}

void print_postorder(TN *t)
{
    if (t == NULL)
        return;

    print_postorder(t->left);  // left
    print_postorder(t->right); // right
    printf("%d ", t->data);    // root
}

int main()
{
    init_tree();

    insert(50);
    insert(30);
    insert(60);
    insert(20);
    insert(15);
    insert(5);
    insert(45);
    insert(75);
    insert(40);
    insert(90);
    insert(65);
    insert(70);
    print_tree(root, 0);

    if (search(65) == NULL)
        printf("%d not found\n", 65);
    else
        printf("%d found\n", 65);

    if (search(95) == NULL)
        printf("%d not found\n", 95);
    else
        printf("%d found\n", 95);

    print_inorder(root);
    printf("\n");

    print_preorder(root);
    printf("\n");

    print_postorder(root);
    printf("\n");

    Delete(5);
    print_tree();

    Delete(70);
    print_tree();

    return 0;
}