B-Tree Deletion — Borrow & Merge

How it works

1. Search for the key, remembering the path. If it is not in the tree, stop.
2. Key in a leaf: remove it.
3. Key in an internal node: replace it with its predecessor (largest key of the left subtree) or successor (smallest key of the right subtree). That key comes from a leaf, so the actual removal happens in a leaf.
4. If the node still has at least the minimum number of keys, you are done.
5. Underflow: if an adjacent sibling has more than the minimum, borrow — the parent's separator moves down into the node and the sibling's nearest key moves up to replace it.
6. Otherwise merge the node, the separator and a sibling into one node. The parent lost a key, so check it next; if the root ends up empty, its only child becomes the new root.

Worked example: borrow, merge and an internal key

This page opens on an order-3 tree, where every non-root node needs at least 1 key: root [40]; below it [20] and [60, 80]; and the leaves [10], [30, 35], [50], [70] and [90].

• Delete 10 — borrow. The leaf [10] becomes empty. Its right sibling [30, 35] has a key to spare, so the parent's separator 20 moves down into the empty leaf and the sibling's smallest key, 30, moves up to replace it: [30] now sits above [20] and [35]. A borrow is a small rotation through the parent; the parent keeps its key count, so a borrow never cascades.
• Delete 70 — merge. The leaf [70] becomes empty and both of its siblings, [50] and [90], are at the minimum. So it merges with its left sibling, and the separator 60 comes down between them: [50, 60]. The parent shrinks from [60, 80] to [80], which is still legal, so the repair stops there.
• Delete 40 — an internal key. 40 is in the root, so it cannot just disappear — its children need a separator. Its predecessor 35, the largest key of the left subtree, sits in [30, 35], which can spare it, so 35 moves up into the root and no repair is needed.

Each case is one click under Delete cases above.

Borrow or merge: how to decide

Look at the immediate siblings — the nodes next to the underflowing one under the same parent.

• If a sibling has more than the minimum, borrow from it (also called rotation or redistribution). For internal nodes the sibling's nearest child pointer moves across together with the key, so every node keeps one more child than keys.
• If every adjacent sibling is at the minimum, merge with one of them. The node's keys, the parent's separator and the sibling's keys always fit into one node: (⌈m/2⌉ − 2) + 1 + (⌈m/2⌉ − 1) ≤ m − 1.

Borrowing is preferred because it is local: the parent keeps its number of keys. A merge removes a key from the parent, which may then underflow in turn — that is how repairs climb towards the root, and how a B-tree loses height when the root's last key is pulled down into a merge.

Predecessor or successor for internal keys?

Either works: both are the keys right next to the deleted one in sorted order, and both always live in leaves. Choosing the side whose leaf has a spare key avoids an underflow altogether, which is what the visualizer's default Smart rule does (predecessor first, then successor). The Pred and Succ options force one side, so you can compare the repairs each choice causes on the same tree — delete 20 above with each rule and the outcomes differ.

Top-down deletion (CLRS) vs bottom-up repair

The visualizer deletes first and repairs on the way back up, like its insert. CLRS gives a single-pass, top-down algorithm instead: before it descends into a child that holds only the minimum t − 1 keys, it tops that child up — borrowing from a sibling or merging with one — so whatever happens below, the child can afford to lose a key and the algorithm never has to walk back up.

Both approaches use the same two moves, borrow and merge, and both cost O(log n); they just apply them at different moments, so the final shapes can differ. Exam answers are usually expected to follow the convention of the course textbook.

Common mistakes

• Deleting an internal key without a replacement. The node would end up with one key too few for its children, and two subtrees would lose their separator.
• Borrowing from a cousin. Only immediate siblings under the same parent share a separator key, so only they can lend.
• Dropping child pointers. When internal nodes borrow or merge, child pointers must move with the keys.
• Not shrinking the tree. When a merge empties the root, the merged child must become the new root — otherwise an empty node is left on top.
• Applying the minimum to the root. The root may hold a single key, and a leaf root may even become empty.

Time and space complexity

B-Tree Deletion in Python

from bisect import bisect_left


class Node:
    def __init__(self, leaf=True):
        self.leaf = leaf
        self.keys = []      # sorted; at most m - 1 of them
        self.children = []  # len(keys) + 1 subtrees when internal


class BTree:
    def __init__(self, m):
        self.m = m                          # order: at most m children per node
        self.max_keys = m - 1
        self.min_keys = (m + 1) // 2 - 1    # ceil(m/2) - 1, for every node but the root
        self.root = Node()

    @staticmethod
    def rank(x, k):
        # i <- #keys in x below k: the child to follow / where k belongs
        return bisect_left(x.keys, k)

    def delete(self, k):
        x, path = self.root, []                 # path: (parent, child index) on the way down
        while True:                             # x, i <- search(T.root, k), remembering the path
            i = self.rank(x, k)
            if i < len(x.keys) and x.keys[i] == k:
                break
            if x.leaf:
                return                          # not found
            path.append((x, i))
            x = x.children[i]
        if x.leaf:
            x.keys.pop(i)                       # leaf case: just remove it
        else:                                   # internal: replace k by its predecessor or successor
            # prefer the side whose leaf can spare a key (then no repair is needed)
            use_pred = (len(self.replacement_path(x, i, True)[1].keys) > self.min_keys
                        or len(self.replacement_path(x, i, False)[1].keys) <= self.min_keys)
            steps, leaf = self.replacement_path(x, i, use_pred)
            x.keys[i] = leaf.keys.pop() if use_pred else leaf.keys.pop(0)   # r moves up
            path += steps
            x = leaf                            # that leaf lost a key
        while path and len(x.keys) < self.min_keys:    # underflow (x is not the root)
            p, j = path.pop()                   # x is p.children[j]
            L = p.children[j - 1] if j > 0 else None
            R = p.children[j + 1] if j + 1 < len(p.children) else None
            if L and len(L.keys) > self.min_keys:       # borrow from the left sibling
                x.keys.insert(0, p.keys[j - 1])         # separator comes down into x
                p.keys[j - 1] = L.keys.pop()            # L's largest key goes up
                if not x.leaf:
                    x.children.insert(0, L.children.pop())
                break
            if R and len(R.keys) > self.min_keys:       # borrow from the right sibling
                x.keys.append(p.keys[j])                # separator comes down into x
                p.keys[j] = R.keys.pop(0)               # R's smallest key goes up
                if not x.leaf:
                    x.children.append(R.children.pop(0))
                break
            a = j - 1 if L else j               # merge children a and a+1 with their separator
            left, right = p.children[a], p.children[a + 1]
            left.keys += [p.keys.pop(a)] + right.keys
            left.children += right.children
            p.children.pop(a + 1)
            x = p                               # p lost a key: check it next
        if not self.root.keys and not self.root.leaf:
            self.root = self.root.children[0]   # empty root: the tree gets one level shorter

    def replacement_path(self, x, i, pred):
        # walk to the leaf holding the predecessor (right-most) or successor (left-most) of x.keys[i]
        j = i if pred else i + 1
        steps, y = [(x, j)], x.children[j]
        while not y.leaf:
            j = len(y.children) - 1 if pred else 0
            steps.append((y, j))
            y = y.children[j]
        return steps, y

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• B-Tree VisualizerB-tree visualizer: insert, search and delete keys in a B-tree of order 3 to 7, watch nodes split, borrow and merge, and see why databases are built on B-trees.
• B-Tree Insertion & SplittingB-tree insertion step by step: find the leaf, insert in sorted order, split a full node around its median and push it up — even to a new root. Animated.
• BST Deletion — All Three CasesHow to delete a node from a binary search tree: the leaf, one-child and two-children cases, in-order successor or predecessor, with an animated example.
• AVL Tree VisualizerAVL tree visualizer: insert and delete keys, watch heights and balance factors update and LL, RR, LR, RL rotations keep every operation O(log n).
• Binary Search Tree VisualizerBinary search tree visualizer: insert, search and delete keys step by step, see why every operation costs O(h), and compare a plain BST with AVL and B-trees.