A binary search tree implementation in C, which includes operations like insertion, search and deletion

main.c

#include "tree.h"
#include <stdio.h>

int main(void)
{
  int numbers[] = {5, 3, 8, 1, 4, 7, 9, 2, 12, 17, 13, 19};
  int length = sizeof(numbers) / sizeof(int);
  Node_ptr tree = NULL;
  for (int index = 0; index < length; index++)
  {
    tree = insert_to_tree(tree, numbers[index]);
  }
  tree = delete_node(tree, 7);
  tree = rotate(tree, 12);
  tree = balance(tree);
  print_two_dimensional(tree, 0);
  print_in_order(tree);
  printf("\n");
  print_pre_order(tree);
  printf("\n");
  print_post_order(tree);
  printf("\n");

  print_presence(search(tree, 6));
  print_presence(search(tree, 1));

  destroy_tree(tree);

  return 0;
}

tree.c

#include "tree.h"
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

void print_array(Array_ptr source)
{
  for (int index = 0; index < source->length; index++)
  {
    printf("%d ", source->numbers[index]);
  }
  printf("\n");
}

void print_two_dimensional(Node_ptr root, int space)
{
  if (root == NULL)
    return;
  print_two_dimensional(root->right, space + 10);
  printf("\n");
  for (int count = 0; count < space; count++)
  {
    printf(" ");
  }
  printf("%d\n", root->value);
  print_two_dimensional(root->left, space + 10);
}

/////////////////////////////////////////////////

void destroy_array(Array_ptr source)
{
  free(source->numbers);
  free(source);
}

void destroy_tree(Node_ptr tree)
{
  if (tree == NULL)
    return;
  Node_ptr left_tree = tree->left;
  Node_ptr right_tree = tree->right;
  free(tree);
  destroy_tree(left_tree);
  destroy_tree(right_tree);
}

/////////////////////////////////////////////////

Node_ptr create_node(int value)
{
  Node_ptr node = malloc(sizeof(Node));
  node->value = value;
  node->left = NULL;
  node->right = NULL;
  return node;
}

/////////////////////////////////////////////////

Node_ptr insert_to_tree(Node_ptr tree, int value)
{
  if (tree == NULL)
    return create_node(value);
  if (value < tree->value)
  {
    tree->left = insert_to_tree(tree->left, value);
    return tree;
  }
  tree->right = insert_to_tree(tree->right, value);
  return tree;
};

void print_in_order(Node_ptr tree)
{
  if (tree == NULL)
    return;
  print_in_order(tree->left);
  printf("%d ", tree->value);
  print_in_order(tree->right);
};

void print_pre_order(Node_ptr tree)
{
  if (tree == NULL)
    return;
  printf("%d ", tree->value);
  print_pre_order(tree->left);
  print_pre_order(tree->right);
};

void print_post_order(Node_ptr tree)
{
  if (tree == NULL)
    return;
  print_post_order(tree->left);
  print_post_order(tree->right);
  printf("%d ", tree->value);
};

Bool search(Node_ptr tree, int value)
{
  if (tree == NULL)
    return False;
  if (tree->value == value)
    return True;
  if (value < tree->value)
    return search(tree->left, value);
  return search(tree->right, value);
};

void print_presence(Bool result)
{
  if (result == True)
  {
    printf("Present\n");
    return;
  }
  printf("Not Present\n");
}

Node_ptr left_rotate(Node_ptr tree)
{
  Node_ptr temp = tree->right;
  tree->right = temp->left;
  temp->left = tree;
  return temp;
}

Node_ptr right_rotate(Node_ptr tree)
{
  Node_ptr temp = tree->left;
  tree->left = temp->right;
  temp->right = tree;
  return temp;
}

Node_ptr rotate(Node_ptr tree, int value)
{
  if (tree == NULL)
    return tree;
  if (tree->left && tree->left->value == value)
    return right_rotate(tree);
  if (tree->right && tree->right->value == value)
    return left_rotate(tree);
  if (value < tree->value)
  {
    tree->left = rotate(tree->left, value);
    return tree;
  }
  tree->right = rotate(tree->right, value);
  return tree;
};

Node_ptr find_min_node(Node_ptr root)
{
  return root->left == NULL ? root : find_min_node(root->left);
}

Node_ptr push_to_last_and_remove(Node_ptr tree)
{
  if (tree->left == NULL && tree->right == NULL)
    return NULL;
  if (tree->left == NULL)
  {
    Node_ptr temp = tree->right;
    free(tree);
    return temp;
  }
  if (tree->right == NULL)
  {
    Node_ptr temp = tree->left;
    free(tree);
    return temp;
  }

  Node_ptr min_node = find_min_node(tree->right);
  tree->value = min_node->value;
  tree->right = delete_node(tree->right, min_node->value);
  return tree;
}

Node_ptr delete_node(Node_ptr tree, int value)
{
  if (tree == NULL)
    return NULL;
  if (value < tree->value)
  {
    tree->left = delete_node(tree->left, value);
    return tree;
  }
  if (value > tree->value)
  {
    tree->right = delete_node(tree->right, value);
    return tree;
  }
  return push_to_last_and_remove(tree);
}

Array_ptr create_array(int count)
{
  Array_ptr array = malloc(sizeof(Array));
  array->numbers = malloc(sizeof(int) * count);
  array->length = 0;
  return array;
}

void track_in_order(Node_ptr tree, Array_ptr traversal)
{
  if (tree == NULL)
    return;
  track_in_order(tree->left, traversal);
  traversal->numbers[traversal->length] = tree->value;
  traversal->length++;
  track_in_order(tree->right, traversal);
}

int find_median_index(int count)
{
  return (count - 1) / 2;
}

int max(int a, int b)
{
  return a > b ? a : b;
}

int find_max_depth(Node_ptr tree)
{
  return tree == NULL ? 0 : max(find_max_depth(tree->left), find_max_depth(tree->right)) + 1;
};

void make_new_insertion_order(Array_ptr source, Array_ptr arr, int start, int end)
{
  if (end - start == 0)
    return;
  int middle_index = find_median_index(end - start);
  arr->numbers[arr->length] = source->numbers[middle_index + start];
  arr->length++;
  make_new_insertion_order(source, arr, start, start + middle_index);
  make_new_insertion_order(source, arr, start + middle_index + 1, end);
};

Node_ptr balance(Node_ptr tree)
{
  Array_ptr in_order_list = create_array(pow(2, find_max_depth(tree)));
  track_in_order(tree, in_order_list);
  Array_ptr ordered_array = create_array(in_order_list->length);
  make_new_insertion_order(in_order_list, ordered_array, 0, in_order_list->length);
  Node_ptr new_tree = NULL;
  for (int index = 0; index < ordered_array->length; index++)
  {
    new_tree = insert_to_tree(new_tree, ordered_array->numbers[index]);
  }
  destroy_array(in_order_list);
  destroy_array(ordered_array);
  destroy_tree(tree);
  return new_tree;
};

tree.h

#ifndef __TREE_H_
#define __TREE_H_

typedef struct node
{
  int value;
  struct node *left;
  struct node *right;
} Node;

typedef struct
{
  int *numbers;
  int length;
} Array;

typedef Array *Array_ptr;

typedef Node *Node_ptr;

typedef enum
{
  False,
  True
} Bool;

Node_ptr push_to_last(Node_ptr tree);
Bool search(Node_ptr tree, int value);
Node_ptr delete_node(Node_ptr tree, int value);
Node_ptr insert_to_tree(Node_ptr tree, int value);
Node_ptr right_rotate(Node_ptr tree);
Node_ptr left_rotate(Node_ptr tree);
Node_ptr rotate(Node_ptr tree, int value);
Node_ptr balance(Node_ptr tree);
Array_ptr create_array(int count);

void track_in_order(Node_ptr tree, Array_ptr traversal);
void print_presence(Bool result);
void destroy_tree(Node_ptr tree);
void print_in_order(Node_ptr tree);
void print_pre_order(Node_ptr tree);
void print_post_order(Node_ptr tree);
void print_two_dimensional(Node_ptr root, int space);

#endif