I have tried to implement my Binary Search Tree in C. The following are the 18 operations defined:

• create a bst
• is_empty
• insert
• delete
• clear
• find
• find_min
• find_max
• height
• size
• depth
• level order traversal
• preorder traversal
• inorder traversal
• postorder traversal
• inorder successor
• is_bst (is the tree a binary search tree)
• is_bst_balanced (is the binary search tree balanced)

This was an important phase in my coding skills to understand what recursion really is. I usually have a table of returns and a recursive call stack both drawn to track the running of recursion, and that helped immensely to grasp the background work of recursion. If you find any improvement to be said about some recursive functions in this BST implementation, I would be grateful to read them through.

This is the entire code. I have included my Queue because I needed for the level_order function.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define max(x, y) (((x) > (y)) ? (x) : (y))

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

//---------------Queue-----------------
typedef struct QNode {
    Node* data;
    struct QNode* next;
} QNode;

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

const Queue queue_init = { .size = 0, .head = NULL, .tail = NULL };

QNode* create_node(Node* elm) {
    QNode* node = malloc(sizeof * node);
    if (!node) return node;
    node->data = elm;
    node->next = NULL;
    return node;
}

int is_empty_q(Queue *q) {
    return q->tail == NULL;
}

QNode* tail_prev(Queue *q) {
    QNode* node = q->head, *prev = NULL;
    while (node->next) {
        prev = node;
        node = node->next;
    }
    return prev;
}

void enqueue(Queue *q, Node* elm) {
    QNode* updated_head = create_node(elm);
    if (!q->head) {
        q->head = updated_head;
        q->tail = q->head;
    }
    else {
        updated_head->next = q->head;
        q->head = updated_head;
    }
    q->size++;
}

Node* dequeue(Queue *q) {
    if (!is_empty_q(q)) {
        QNode* node = q->tail;
        Node* elm = q->tail->data;
        q->tail = tail_prev(q);
        if (q->tail) {
            q->tail->next = NULL;
        }
        else {
            q->head = NULL;
        }
        free(node);
        q->size--;
        return elm;
    }
    return NULL; 
}

Node* front(Queue *q) {
    Node* front;
    if (q->tail)
        front = q->tail->data;
    else
        front = NULL;
    return front;
}

void clear_q(Queue *q) {
    while (q->tail)
        dequeue(q);
    printf("Queue Cleared");
}

//---------------BST------------------
typedef struct BST {
    Node* root;
} BST;
 
const BST bst_init = { .root = NULL };

Node* create_node_bst(int elm) {
    Node* node = malloc(sizeof * node);
    if (!node) return node;
    node->data = elm;
    node->left = node->right = NULL;
    return node;
}

BST* create_bst() {
    BST* bst = malloc(sizeof * bst);
    if (!bst) return bst;
    bst->root = NULL;
    return bst;
}

int is_empty(Node* root) {
    return root == NULL;
}

Node* insert(Node* root, int elm) { // -V
    if (!root) {
        root = create_node_bst(elm);
    }
    else if (elm <= root->data) {
        root->left = insert(root->left, elm);
    }
    else {
        root->right = insert(root->right, elm);
    }
    return root;
}

Node* find(Node* root, int elm) { // -V
    if (!is_empty(root)) {
        if (!root) {
            root = NULL;
        }
        else if (root->data == elm) {
            root = root;
        }
        else if (elm <= root->data) {
            root = find(root->left, elm);
        }
        else {
            root = find(root->right, elm);
        }
        return root;
    }
    else
        return root;
}

Node* find_max(Node* root) { //-V
    if (!is_empty(root)) {
        if (root->right == NULL)
            return root;
        else {
            return find_max(root->right);
        }
    }
    else
        return root;
}

Node* find_min(Node* root) { //-V
    if (!is_empty(root)) {
        if (!root->left)
            return root;
        else {
            return find_min(root->left);
        }
    }
    else
        return root;
}

int height(Node* root) { 
    if (root == NULL) {
        return -1; // 0 if heighe is number of edges, or -1 if height=number of edges
    }
    int left_height = height(root->left);
    int right_height = height(root->right);
    return max(left_height, right_height) + 1;
}

int depth(Node* root, int elm) {
    if (root->data == elm) {
        return 0;
    }
    else if (elm < root->data) {
        return depth(root->left, elm) + 1;
    }
    else {
        return depth(root->right, elm) + 1;
    }
}

Node* delete(Node* root, int elm) { 
    if (root == NULL)
        return root;
    else if (elm > root->data)
        root->right = delete(root->right, elm);
    else if (elm < root->data)
        root->left = delete(root->left, elm);
    else { // elm found
        if (root->left == NULL && root->right == NULL) {
            free(root);
            root = NULL;
        }
        else if (root->left == NULL) {
            Node* temp = root;
            root = root->right;
            free(temp);            
        }
        else if (root->right == NULL) {
            Node* temp = root;
            root = root->left;
            free(temp);
        }
        else { //this case is done until it is reduced to one of the previous three cases
            Node* temp = find_min(root->right);
            root->data = temp->data;
            root->right = delete(root->right, elm);
        }
    }
    return root;
}

int is_bst(Node* root, int min, int max) { // solution 1
    if (root == NULL) {
        return 1;
    }
    else if (root->data < max && root->data > min && is_bst(root->left, min, root->data) && is_bst(root->right, root->data, max))
        return 1;
    else
        return 0; 
} // solution 2, traverse inorder and check if the list is sorted

int is_bst_balanced(Node* root) {
    int is_balanced = 1;
    int left_height = height(root->left);
    int right_height = height(root->right);
    if (abs(right_height - left_height) > 1)
        is_balanced = 0;
    return is_balanced;
}

int size(Node* root) {
    if (!root)
        return 0;
    int left_size = size(root->left);
    int right_size = size(root->right);
    return left_size + right_size + 1; // + 1 is for the ancesstor
}

void level_order(Node* root) { // visit all children before grand children
    if (!is_empty(root)) {
        Queue *q = malloc(sizeof *q);
        if (q) {
            *q = queue_init;
            enqueue(q, root);
            while (!is_empty_q(q)) {
                Node* cur = front(q);
                printf("%d ", cur->data);
                if (cur->left != NULL)
                    enqueue(q, cur->left);
                if (cur->right != NULL)
                    enqueue(q, cur->right);
                dequeue(q);
            }
        }
    }
}

void pre_order(Node* root) { //D<root>L<left>R<right> -- preorder (of root)
    if (root) {
        printf("%d ", root->data);
        pre_order(root->left);
        pre_order(root->right);
    }
}

void in_order(Node* root) { //L<left>D<root>R<right> -- inorder -- gives sorted list
    if (root) {
        in_order(root->left);
        printf("%d ", root->data);
        in_order(root->right);
    }
}

Node* in_order_suc(Node* root, int data) { 
    Node* cur = find(root, data);
    if (!cur) 
        return cur;
    if (cur->right != NULL) { //case 1: node has sub tree
        return find_min(cur->right);
    }
    else { //case 2: no right sub tree
        Node* suc = NULL, *prev = root;
        while (prev != cur) {
            if (cur->data < prev->data) {
                suc = prev;
                prev = prev->left;
            }
            else {
                prev = prev->right;
            }
        }
        return suc;
    }
}

void post_order(Node* root) { //L<left>R<right>R<root> -- postorder
    if (root) {
        post_order(root->left);
        post_order(root->right);
        printf("%d ", root->data);
    }
}

Node* clear(Node* root) {
    while (root) {
        root = delete(root, root->data);
    }
    return root;
}

int main() {
    #define MAX 8
    int n = MAX;
    BST bst1 = bst_init;
    Node* bst1_root = bst1.root;
    int arr[MAX] = {15, 10, 20, 9, 13, 19, 22, 18};
    if (!arr) return 0;
    for (int i = 0; i < n; i++)
        bst1_root = insert(bst1_root, arr[i]);
    
    printf("height: %d \n", height(bst1_root));
    printf("size: %d \n", size(bst1_root));
    printf("depth of 13: %d \n", depth(bst1_root, 18));
    printf("is_bst: %d \n", is_bst(bst1_root, -1000, 1000)); //assuming -1000 < data(bst) < 1000
    printf("is_bst_balanced: %d \n", is_bst_balanced(bst1_root));
    printf("min: %d \n", find_min(bst1_root)->data);
    printf("max: %d \n", find_max(bst1_root)->data);
    printf("element: %d found \n", find(bst1_root, 19)->data);
    printf("level order ");
    level_order(bst1_root);
    printf("\n");
    printf("preorder order ");
    pre_order(bst1_root);
    printf("\n");
    printf("inorder order ");
    in_order(bst1_root);
    printf("\n");
    printf("postorder order ");
    post_order(bst1_root);
    printf("\n");
    printf("inorder successor of 9 is %d \n", in_order_suc(bst1_root, 9)->data);
    bst1_root = delete(bst1_root, 18);
    printf("in order ");
    in_order(bst1_root);
    printf("\n");
    bst1_root = insert(bst1_root, 18);
    printf("in order ");
    in_order(bst1_root);
    bst1_root = clear(bst1_root);
    printf("\n");
    if (!bst1_root)
        printf("BST Cleared!");
    return 0;
}