Deletion in B-Tree in Java

import java.util.*;

class BTreeNode {
    int t; // Minimum degree
    int[] keys;
    BTreeNode[] children;
    int n;
    boolean leaf;

    BTreeNode(int t, boolean leaf) {
        this.t = t;
        this.leaf = leaf;
        this.keys = new int[2 * t - 1];
        this.children = new BTreeNode[2 * t];
        this.n = 0;
    }

    // Find key index
    int findKey(int k) {
        int idx = 0;
        while (idx < n && keys[idx] < k)
            ++idx;
        return idx;
    }

    // Remove key
    void remove(int k) {
        int idx = findKey(k);

        // Case 1: Key present in node
        if (idx < n && keys[idx] == k) {
            if (leaf)
                removeFromLeaf(idx);
            else
                removeFromNonLeaf(idx);
        } else {
            // If node is leaf
            if (leaf) {
                System.out.println("Key not found");
                return;
            }

            boolean flag = (idx == n);

            if (children[idx].n < t)
                fill(idx);

            if (flag && idx > n)
                children[idx - 1].remove(k);
            else
                children[idx].remove(k);
        }
    }

    void removeFromLeaf(int idx) {
        for (int i = idx + 1; i < n; ++i)
            keys[i - 1] = keys[i];
        n--;
    }

    void removeFromNonLeaf(int idx) {
        int k = keys[idx];

        if (children[idx].n >= t) {
            int pred = getPred(idx);
            keys[idx] = pred;
            children[idx].remove(pred);
        } else if (children[idx + 1].n >= t) {
            int succ = getSucc(idx);
            keys[idx] = succ;
            children[idx + 1].remove(succ);
        } else {
            merge(idx);
            children[idx].remove(k);
        }
    }

    int getPred(int idx) {
        BTreeNode cur = children[idx];
        while (!cur.leaf)
            cur = cur.children[cur.n];
        return cur.keys[cur.n - 1];
    }

    int getSucc(int idx) {
        BTreeNode cur = children[idx + 1];
        while (!cur.leaf)
            cur = cur.children[0];
        return cur.keys[0];
    }

    void fill(int idx) {
        if (idx != 0 && children[idx - 1].n >= t)
            borrowFromPrev(idx);
        else if (idx != n && children[idx + 1].n >= t)
            borrowFromNext(idx);
        else {
            if (idx != n)
                merge(idx);
            else
                merge(idx - 1);
        }
    }

    void borrowFromPrev(int idx) {
        BTreeNode child = children[idx];
        BTreeNode sibling = children[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.children[i + 1] = child.children[i];
        }

        child.keys[0] = keys[idx - 1];

        if (!child.leaf)
            child.children[0] = sibling.children[sibling.n];

        keys[idx - 1] = sibling.keys[sibling.n - 1];

        child.n += 1;
        sibling.n -= 1;
    }

    void borrowFromNext(int idx) {
        BTreeNode child = children[idx];
        BTreeNode sibling = children[idx + 1];

        child.keys[child.n] = keys[idx];

        if (!child.leaf)
            child.children[child.n + 1] = sibling.children[0];

        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.children[i - 1] = sibling.children[i];
        }

        child.n += 1;
        sibling.n -= 1;
    }

    void merge(int idx) {
        BTreeNode child = children[idx];
        BTreeNode sibling = children[idx + 1];

        child.keys[t - 1] = 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.children[i + t] = sibling.children[i];
        }

        for (int i = idx + 1; i < n; ++i)
            keys[i - 1] = keys[i];

        for (int i = idx + 2; i <= n; ++i)
            children[i - 1] = children[i];

        child.n += sibling.n + 1;
        n--;
    }
}

class BTree {
    BTreeNode root;
    int t;

    BTree(int t) {
        this.root = null;
        this.t = t;
    }

    void remove(int k) {
        if (root == null) {
            System.out.println("Tree is empty");
            return;
        }

        root.remove(k);

        if (root.n == 0) {
            if (root.leaf)
                root = null;
            else
                root = root.children[0];
        }
    }

    public static void main(String[] args) {
        BTree tree = new BTree(3);

        // Example usage can be extended with insertion logic
        System.out.println("B-Tree deletion demo");
    }
}