// Binary search tree — common operations in C (linked nodes).
// search, insert, delete; min/max; successor and predecessor (inorder neighbors).
// Assume distinct keys. Compile: gcc -std=c11 binary-search-tree-operations-demo.c -o bst_ops_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);
}

// Smallest key in subtree
static Node *minNode(Node *root) {
    if (!root) {
        return NULL;
    }
    Node *cur = root;
    while (cur->left) {
        cur = cur->left;
    }
    return cur;
}

// Largest key in subtree
static Node *maxNode(Node *root) {
    if (!root) {
        return NULL;
    }
    Node *cur = root;
    while (cur->right) {
        cur = cur->right;
    }
    return cur;
}

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);
}

// Iterative BST search (same logic, no recursion)
Node *searchIter(Node *root, int key) {
    while (root && root->data != key) {
        if (key < root->data) {
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return root;
}

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);
}

// Next larger key in sorted order (NULL if none). Key must exist in tree.
Node *successor(Node *root, int key) {
    Node *succ = NULL;
    while (root) {
        if (key < root->data) {
            succ = root;
            root = root->left;
        } else if (key > root->data) {
            root = root->right;
        } else {
            if (root->right) {
                return minNode(root->right);
            }
            return succ;
        }
    }
    return NULL;
}

// Next smaller key in sorted order (NULL if none). Key must exist in tree.
Node *predecessor(Node *root, int key) {
    Node *pred = NULL;
    while (root) {
        if (key > root->data) {
            pred = root;
            root = root->right;
        } else if (key < root->data) {
            root = root->left;
        } else {
            if (root->left) {
                return maxNode(root->left);
            }
            return pred;
        }
    }
    return NULL;
}

static void printSuccPred(Node *root, int key) {
    if (!search(root, key)) {
        printf("key %d not in tree — skip succ/pred\n", key);
        return;
    }
    Node *s = successor(root, key);
    Node *p = predecessor(root, key);
    printf("key %d: successor ", key);
    if (s) {
        printf("%d", s->data);
    } else {
        printf("(none)");
    }
    printf(", predecessor ");
    if (p) {
        printf("%d", p->data);
    } else {
        printf("(none)");
    }
    printf("\n");
}

int main(void) {
    printf("=== BST operations demo ===\n\n");

    Node *root = NULL;
    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: ");
    inorder(root);
    printf("\n");

    Node *mn = minNode(root);
    Node *mx = maxNode(root);
    printf("min = %d, max = %d\n", mn ? mn->data : -1, mx ? mx->data : -1);

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

    printf("\nSuccessor / predecessor (inorder neighbors):\n");
    printSuccPred(root, 40);
    printSuccPred(root, 50);
    printSuccPred(root, 20);
    printSuccPred(root, 80);

    printf("\nDelete 20 (leaf), then show succ(30):\n");
    root = deleteNode(root, 20);
    printSuccPred(root, 30);

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