// Binary search tree (BST) — linked-list / pointer representation in C.
// Ordering: left subtree keys < root key < right subtree keys (assume distinct keys).
// Implements search, insert, delete (classic three cases), inorder walk (sorted order).
// Compile: gcc -std=c11 binary-search-tree-linkedlist-demo.c -o bst_ll_demo

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

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

static Node *createNode(int data) {
    Node *n = (Node *)malloc(sizeof(Node));
    if (!n) {
        perror("malloc");
        exit(EXIT_FAILURE);
    }
    n->data = data;
    n->left = n->right = NULL;
    return n;
}

static void freeTree(Node *root) {
    if (!root) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

// Return node with key, or NULL
Node *search(Node *root, int key) {
    if (!root || root->data == key) {
        return root;
    }
    if (key < root->data) {
        return search(root->left, key);
    }
    return search(root->right, key);
}

// Smallest node in subtree (used for successor step in delete)
static Node *minNode(Node *root) {
    if (!root) {
        return NULL;
    }
    Node *cur = root;
    while (cur->left) {
        cur = cur->left;
    }
    return cur;
}

Node *insert(Node *root, int key) {
    if (!root) {
        return createNode(key);
    }
    if (key < root->data) {
        root->left = insert(root->left, key);
    } else if (key > root->data) {
        root->right = insert(root->right, key);
    }
    return root;
}

Node *deleteNode(Node *root, int key) {
    if (!root) {
        return NULL;
    }
    if (key < root->data) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->data) {
        root->right = deleteNode(root->right, key);
    } else {
        if (!root->left) {
            Node *t = root->right;
            free(root);
            return t;
        }
        if (!root->right) {
            Node *t = root->left;
            free(root);
            return t;
        }
        Node *succ = minNode(root->right);
        root->data = succ->data;
        root->right = deleteNode(root->right, succ->data);
    }
    return root;
}

void inorder(Node *root) {
    if (!root) {
        return;
    }
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

static int treeHeight(Node *root) {
    if (!root) {
        return 0;
    }
    int lh = treeHeight(root->left);
    int rh = treeHeight(root->right);
    return (lh > rh ? lh : rh) + 1;
}

int main(void) {
    printf("=== Binary search tree (linked list) demo ===\n\n");

    Node *root = NULL;

    printf("Insert: 50, 30, 70, 20, 40, 60, 80\n");
    int keys[] = {50, 30, 70, 20, 40, 60, 80};
    for (size_t i = 0; i < sizeof(keys) / sizeof(keys[0]); i++) {
        root = insert(root, keys[i]);
    }

    printf("Inorder (sorted): ");
    inorder(root);
    printf("\nHeight: %d\n", treeHeight(root));

    printf("\nSearch 40: %s\n", search(root, 40) ? "found" : "not found");
    printf("Search 99: %s\n", search(root, 99) ? "found" : "not found");

    printf("\nDelete leaf 20\n");
    root = deleteNode(root, 20);
    printf("Inorder: ");
    inorder(root);
    printf("\n");

    printf("\nDelete node with one child (30 had only right subtree after 20 removed)\n");
    root = deleteNode(root, 30);
    printf("Inorder: ");
    inorder(root);
    printf("\n");

    printf("\nDelete node with two children (50)\n");
    root = deleteNode(root, 50);
    printf("Inorder: ");
    inorder(root);
    printf("\n");

    printf("\nFinal height: %d\n", treeHeight(root));

    freeTree(root);
    printf("\nDone.\n");
    return 0;
}