cannot delete key from node with minimum number of keys

Error message

cannot delete key from node with minimum number of keys

What it means

Delete refuses to recurse into a child that is already at the minimum key count, because removing a key from it would underflow the node and there is no planned rebalance at this point. Before recursing, Delete should have borrowed from a sibling or merged; hitting this panic means that descent-time rebalancing was skipped or the node was already underfull.

Source

Thrown at structure/tree/btree.go:342

			// Take a key from the right sibling. Mirrors the transformation above for taking a key from the left sibling.
			right := node.children[i+1]
			child.Append(node.keys[i], right.children[0])
			node.keys[i] = right.keys[0]
			right.children[0] = right.children[1]
			right.DeleteIthKey(0)
		} else {
			if i == 0 {
				// Merge with right sibling
				node.Merge(i)
			} else {
				// Merge with left sibling
				node.Merge(i - 1)
				child = node.children[i-1]
			}
		}
	}
	if child.numKeys == minKeys {
		panic("cannot delete key from node with minimum number of keys")
	}
	child.Delete(tree, key)
}

func (tree *BTree[T]) Delete(key T) {
	if tree.root == nil {
		return
	}
	tree.root.Delete(tree, key)
	if tree.root.numKeys == 0 {
		tree.root = tree.root.children[0]
	}
}

View on GitHub (pinned to 5ba447ec5f)

Solutions

Ensure the tree is built and maintained exclusively via tree.Insert/tree.Delete.
Rebuild the tree (collect and re-insert keys) if nodes may be underfull.
Run root.Verify(tree) before deleting to detect underfull nodes.
Do not mix nodes between trees with different maxKeys.

Example fix

// before
node.DeleteIthKey(0) // underflows, later Delete panics
// after
tree.Delete(key) // rebalances during descent

Defensive patterns

Strategy: validation

Validate before calling

func canDeleteFrom[T constraints.Ordered](t *BTree[T]) bool {
    if t.root == nil { return false }
    minK := (t.maxKeys - 1) / 2
    var walk func(n *BTreeNode[T]) bool
    walk = func(n *BTreeNode[T]) bool {
        if n != t.root && n.numKeys < minK { return false }
        for _, c := range n.children[:n.numKeys+1] { if !walk(c) { return false } }
        return true
    }
    return walk(t.root)
}
if !canDeleteFrom(tree) { tree = rebuild(tree) }
tree.Delete(key)

Try / catch

defer func() {
    if r := recover(); r != nil {
        tree = rebuildTreeFromKeys(tree)
    }
}()

Prevention

Avoid manual node-level deletions that underflow nodes
Never share nodes between trees with different maxKeys
Run Verify before delete-heavy workloads

When it happens

Trigger: Calling tree.Delete on a tree with underfull nodes created by direct mutation; a descent path where predecessor/successor borrow branches were not taken (single-child situations) leaving the child at minKeys.

Common situations: Custom delete wrappers that call node-level methods first; trees reconstructed from partial data; nodes shared across trees with different maxKeys making minKeys inconsistent.

Related errors

AI-assisted analysis of TheAlgorithms/Go@5ba447ec5f (2026-09-02). Data as JSON: /api/errors/7632ff1db7bcad49. Report an issue: GitHub.