TheAlgorithms/Go · error

nodes should not have less than the minimum number of keys

Error message

nodes should not have less than the minimum number of keys

What it means

During Delete, when both the left and right siblings of the key's child have the minimum number of keys, the code merges them — but if either actually has FEWER than minKeys, the invariant was already broken and the merge would produce an invalid node, so it panics. This indicates earlier corruption or manual key removal.

Source

Thrown at structure/tree/btree.go:290

				//  A c C
				//   /
				// a b
				replacementKey := left.Max()
				node.keys[i] = replacementKey
				left.Delete(tree, replacementKey)
			} else if right.numKeys > minKeys {
				// Replace the key we want to delete with the min key from the right
				// subtree. Then delete that key in the right subtree. Mirrors the
				// transformation above for replacing from the left subtree.
				replacementKey := right.Min()
				node.keys[i] = replacementKey
				right.Delete(tree, replacementKey)
			} else {
				// Both left and right subtrees have the minimum number of keys. Merge
				// the left tree, the deleted key, and the right tree together into the
				// left tree. Then recursively delete the key in the left tree.
				if left.numKeys != minKeys || right.numKeys != minKeys {
					panic("nodes should not have less than the minimum number of keys")
				}
				node.Merge(i)
				left.Delete(tree, key)
			}
			return
		}

		if key < node.keys[i] {
			break
		}
	}

	// Case 3: key may exist in a child node.
	child := node.children[i]
	if child.numKeys == minKeys {
		// Before we recurse into the child node, make sure it has more than
		// the minimum number of keys.
		if i > 0 && node.children[i-1].numKeys > minKeys {

View on GitHub (pinned to 5ba447ec5f)

Solutions

1. Only mutate the tree through tree.Insert/tree.Delete.
2. Rebuild the tree from its keys if it may be corrupted: collect keys and re-insert into a fresh BTree.
3. Verify invariants with root.Verify(tree) before deleting to catch corruption early.
4. Ensure consistent maxKeys across all nodes and trees.

Example fix

// before
tree.Delete(k) // panics on corrupted tree
// after
keys := tree.Keys() // snapshot via in-order walk
fresh := NewBTree[int](tree.maxKeys)
for _, k := range keys { fresh.Insert(k) }
fresh.Delete(k)

func treeHealthy[T constraints.Ordered](t *BTree[T]) (ok bool) {
    defer func() { ok = recover() == nil }()
    if t.root != nil { t.root.Verify(t) }
    return
}
if !treeHealthy(tree) { tree = rebuild(tree) }
tree.Delete(key)

func safeDelete[T constraints.Ordered](t *BTree[T], k T) {
    defer func() {
        if r := recover() != nil; r { _ = r; t2 := rebuild(t); t2.Delete(k); *t = *t2 }
    }()
    t.Delete(k)
}

When it happens

Trigger: Calling tree.Delete on a tree whose nodes were previously underflowed (e.g. via direct DeleteIthKey calls or reflection-based mutation); reusing nodes from a tree with a different maxKeys so minKeys does not match.

Common situations: Manually pruned nodes in tests; serialization round-trips that dropped keys; mixing trees with different maxKeys parameters.

Related errors

• node has too few keys
• node has too many keys
• cannot delete key from node with minimum number of keys
• BTree maxKeys cannot be zero
• Must be >= 3 keys

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