I am working on implementing a non-preemptive splitting insert function for a B-Tree in C. Below is the structure of my B-tree node:

#define KEYS_NUMBER     4                   // Max number of keys in a node
#define MIN_KEYS        (KEYS_NUMBER / 2)   // Min number of keys in a node
#define CHILDREN_NUMBER (KEYS_NUMBER + 1)   // Max number of children in a node

typedef struct node {
    bool leaf;
    int n;
    int keys[KEYS_NUMBER];
    struct node *children[CHILDREN_NUMBER];
} Node;

I have the following code for my insertNonFull and insertKey functions:

void insertNonFull(Node *node, int key) {
    int i = node->n - 1;

    if (node->leaf) {
        while (i >= 0 && (key < node->keys[i])) {
            node->keys[i + 1] = node->keys[i];
            i--;
        }
        node->keys[i + 1] = key;
        node->n = node->n + 1;
    } else {
        while (i >= 0 && key < node->keys[i]) {
            i--;
        }
        i++;
        if (node->children[i]->n == KEYS_NUMBER) {
            splitChild(node, i, node->children[i]);
            if (key > node->keys[i]) {
                i++;
            }
        }
        insertNonFull(node->children[i], key);
    }
}

void insertKey(Node **tree, int key) {
    Node *r = *tree;

    if (r->n == KEYS_NUMBER) {
        Node *s = createNode();
        *tree = s;
        s->leaf = false;
        s->n = 0;
        s->children[0] = r;
        splitChild(s, 0, r);
        insertNonFull(s, key);
    } else {
        insertNonFull(r, key);
    }
}

When I add the key 15, the B-tree structure before and after the insertion is as follows:

Before inserting the 15th key:

[3, 6, 9, 12]
    [1, 2]
    [4, 5]
    [7, 8]
    [10, 11]
    [13, 14]

After inserting the 15th key:

[9]
    [3, 6]
        [1, 2]
        [4, 5]
        [7, 8]
    [12]
        [10, 11]
        [13, 14, 15]

We can see that the root node splits prematurely. How can I optimize my insert function to prevent this premature split and achieve the following result instead?

[3, 6, 9, 12]
    [1, 2]
    [4, 5]
    [7, 8]
    [10, 11]
    [13, 14, 15]

Any suggestions on how to adjust my insertNonFull and insertKey functions to achieve this?