#include <stdio.

h>
#include <stdlib.h>
#include <stdbool.h>

#define T 3 // Minimum degree

typedef struct BTreeNode {

int keys[2*T - 1];
struct BTreeNode *child[2*T];
int n;
bool leaf;
} BTreeNode;

// Function prototypes
BTreeNode* createNode(bool leaf);
void traverse(BTreeNode* root);
BTreeNode* search(BTreeNode* root, int k);
void insert(BTreeNode** root, int k);
void insertNonFull(BTreeNode* x, int k);
void splitChild(BTreeNode* x, int i, BTreeNode* y);
void deleteKey(BTreeNode** root, int k);
void deleteFromNode(BTreeNode* x, int k);
int findKey(BTreeNode* x, int k);
int getPred(BTreeNode* x, int idx);
int getSucc(BTreeNode* x, int idx);
void fill(BTreeNode* x, int idx);
void borrowFromPrev(BTreeNode* x, int idx);
void borrowFromNext(BTreeNode* x, int idx);
void merge(BTreeNode* x, int idx);

BTreeNode* createNode(bool leaf) {

BTreeNode* node = (BTreeNode*)malloc(sizeof(BTreeNode));
node->leaf = leaf;
node->n = 0;
for (int i = 0; i < 2*T; i++)
node->child[i] = NULL;
return node;
}
void traverse(BTreeNode* root) {
if (root) {
int i;
for (i = 0; i < root->n; i++) {
if (!root->leaf)
traverse(root->child[i]);
printf("%d ", root->keys[i]);
}
if (!root->leaf)
traverse(root->child[i]);
}
}

BTreeNode* search(BTreeNode* root, int k) {

int i = 0;
while (i < root->n && k > root->keys[i])
i++;
if (i < root->n && root->keys[i] == k)
return root;
if (root->leaf)
return NULL;
return search(root->child[i], k);
}

void insert(BTreeNode** root, int k) {

BTreeNode* r = *root;
if (r->n == 2*T - 1) {
BTreeNode* s = createNode(false);
s->child[0] = r;
splitChild(s, 0, r);
int i = 0;
if (s->keys[0] < k) i++;
insertNonFull(s->child[i], k);
*root = s;
} else {
insertNonFull(r, k);
}
}
void insertNonFull(BTreeNode* x, int k) {
int i = x->n - 1;
if (x->leaf) {
while (i >= 0 && x->keys[i] > k) {
x->keys[i+1] = x->keys[i];
i--;
}
x->keys[i+1] = k;
x->n++;
} else {
while (i >= 0 && x->keys[i] > k) i--;
i++;
if (x->child[i]->n == 2*T - 1) {
splitChild(x, i, x->child[i]);
if (x->keys[i] < k) i++;
}
insertNonFull(x->child[i], k);
}
}

void splitChild(BTreeNode* x, int i, BTreeNode* y) {

BTreeNode* z = createNode(y->leaf);
z->n = T - 1;
for (int j = 0; j < T-1; j++)
z->keys[j] = y->keys[j+T];
if (!y->leaf) {
for (int j = 0; j < T; j++)
z->child[j] = y->child[j+T];
}
y->n = T - 1;
for (int j = x->n; j >= i+1; j--)
x->child[j+1] = x->child[j];
x->child[i+1] = z;
for (int j = x->n-1; j >= i; j--)
x->keys[j+1] = x->keys[j];
x->keys[i] = y->keys[T-1];
x->n++;
}
int findKey(BTreeNode* x, int k) {
int idx = 0;
while (idx < x->n && x->keys[idx] < k)
++idx;
return idx;
}

void deleteKey(BTreeNode** root, int k) {

if (!*root) return;
deleteFromNode(*root, k);
if ((*root)->n == 0) {
BTreeNode* tmp = *root;
if ((*root)->leaf)
*root = NULL;
else
*root = (*root)->child[0];
free(tmp);
}
}

void deleteFromNode(BTreeNode* x, int k) {

int idx = findKey(x, k);
if (idx < x->n && x->keys[idx] == k) {
if (x->leaf) { // Case 1
for (int i = idx+1; i < x->n; ++i)
x->keys[i-1] = x->keys[i];
x->n--;
} else { // Case 2
if (x->child[idx]->n >= T) {
int pred = getPred(x, idx);
x->keys[idx] = pred;
deleteFromNode(x->child[idx], pred);
} else if (x->child[idx+1]->n >= T) {
int succ = getSucc(x, idx);
x->keys[idx] = succ;
deleteFromNode(x->child[idx+1], succ);
} else {
merge(x, idx);
deleteFromNode(x->child[idx], k);
 }
}
} else {
if (x->leaf) return; // Key not in tree
bool flag = (idx == x->n);
if (x->child[idx]->n < T)
fill(x, idx);
if (flag && idx > x->n)
deleteFromNode(x->child[idx-1], k);
else
deleteFromNode(x->child[idx], k);
}
}

int getPred(BTreeNode* x, int idx) {

BTreeNode* cur = x->child[idx];
while (!cur->leaf)
cur = cur->child[cur->n];
return cur->keys[cur->n - 1];
}

int getSucc(BTreeNode* x, int idx) {

BTreeNode* cur = x->child[idx+1];
while (!cur->leaf)
cur = cur->child[0];
return cur->keys[0];
}

void fill(BTreeNode* x, int idx) {

if (idx != 0 && x->child[idx-1]->n >= T)
borrowFromPrev(x, idx);
else if (idx != x->n && x->child[idx+1]->n >= T)
borrowFromNext(x, idx);
else {
if (idx != x->n)
merge(x, idx);
else
merge(x, idx-1);
}
}

void borrowFromPrev(BTreeNode* x, int idx) {

BTreeNode* child = x->child[idx];
BTreeNode* sibling = x->child[idx-1];
for (int i = child->n - 1; i >= 0; --i)
child->keys[i+1] = child->keys[i];
if (!child->leaf) {
for (int i = child->n; i >= 0; --i)
child->child[i+1] = child->child[i];
}
child->keys[0] = x->keys[idx-1];
if (!child->leaf)
child->child[0] = sibling->child[sibling->n];
x->keys[idx-1] = sibling->keys[sibling->n - 1];
child->n += 1;
sibling->n -= 1;
}

void borrowFromNext(BTreeNode* x, int idx) {

BTreeNode* child = x->child[idx];
BTreeNode* sibling = x->child[idx+1];
child->keys[child->n] = x->keys[idx];
if (!child->leaf)
child->child[child->n + 1] = sibling->child[0];
x->keys[idx] = sibling->keys[0];
for (int i = 1; i < sibling->n; ++i)
sibling->keys[i-1] = sibling->keys[i];
if (!sibling->leaf) {
for (int i = 1; i <= sibling->n; ++i)
sibling->child[i-1] = sibling->child[i];
}
child->n += 1;
sibling->n -= 1;
}

void merge(BTreeNode* x, int idx) {

BTreeNode* child = x->child[idx];
BTreeNode* sibling = x->child[idx+1];
 child->keys[T-1] = x->keys[idx];
for (int i = 0; i < sibling->n; ++i)
child->keys[i+T] = sibling->keys[i];
if (!child->leaf) {
for (int i = 0; i <= sibling->n; ++i)
child->child[i+T] = sibling->child[i];
}
for (int i = idx+1; i < x->n; ++i)
x->keys[i-1] = x->keys[i];
for (int i = idx+2; i <= x->n; ++i)
x->child[i-1] = x->child[i];
child->n += sibling->n + 1;
x->n--;
free(sibling);
}

// Driver program
int main() {
BTreeNode* root = createNode(true);

int values[] = {10, 20, 5, 6, 12, 30, 7, 17};

for (int i = 0; i < 8; i++)
insert(&root, values[i]);

printf("B-Tree traversal: ");

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

deleteKey(&root, 6);
printf("After deleting 6: ");
traverse(root);
printf("\n");

deleteKey(&root, 13);
printf("After deleting 13 (not present): ");
traverse(root);
printf("\n");

deleteKey(&root, 7);
 printf("After deleting 7: ");
traverse(root);
printf("\n");

deleteKey(&root, 4);
printf("After deleting 4 (not present): ");
traverse(root);
printf("\n");

deleteKey(&root, 2);
printf("After deleting 2 (not present): ");
traverse(root);
printf("\n");

deleteKey(&root, 16);
printf("After deleting 16 (not present): ");
traverse(root);
printf("\n");

return 0;
}

Output:
B-Tree traversal: 5 6 7 10 12 17 20 30
After deleting 6: 5 7 10 12 17 20 30
After deleting 13 (not present): 5 7 10 12 17 20 30
After deleting 7: 5 10 12 17 20 30
After deleting 4 (not present): 5 10 12 17 20 30
After deleting 2 (not present): 5 10 12 17 20 30
After deleting 16 (not present): 5 10 12 17 20 30

=== Code Execution Successful ===