TheAlgorithms/Go · error

node has too few keys

Error message

node has too few keys

What it means

Verify panics when a non-root node holds fewer keys than minKeys = (maxKeys-1)/2, violating the B-tree minimum occupancy invariant that Delete must maintain via borrow/merge. It indicates the tree's internal rebalancing was bypassed or the node was mutated incorrectly.

Source

Thrown at structure/tree/btree.go:48

		children: make([]*BTreeNode[T], maxKeys+1),
		isLeaf:   isLeaf,
	}
}

func NewBTree[T constraints.Ordered](maxKeys int) *BTree[T] {
	if maxKeys <= 2 {
		panic("Must be >= 3 keys")
	}
	return &BTree[T]{
		root:    nil,
		maxKeys: maxKeys,
	}
}

func (node *BTreeNode[T]) Verify(tree *BTree[T]) {
	minKeys := minKeys(tree.maxKeys)
	if node != tree.root && node.numKeys < minKeys {
		panic("node has too few keys")
	} else if node.numKeys > tree.maxKeys {
		panic("node has too many keys")
	}
}

func (node *BTreeNode[T]) IsFull(maxKeys int) bool {
	return node.numKeys == maxKeys
}

func (node *BTreeNode[T]) Search(key T) bool {
	i := 0
	for ; i < node.numKeys; i++ {
		if key == node.keys[i] {
			return true
		}
		if key < node.keys[i] {
			break
		}

View on GitHub (pinned to 5ba447ec5f)

Solutions

1. Use only the public BTree API (Insert/Delete) and never mutate node fields directly.
2. Ensure all nodes in a tree were created with the same maxKeys as the tree.
3. Call tree.root.Verify(tree) after suspicious operations to find the invariant break point.
4. If you need arbitrary key removal, add rebalancing (borrow/merge) after DeleteIthKey.

Example fix

// before
node.DeleteIthKey(0) // may underflow the node
// after
tree.Delete(key) // maintains B-tree invariants

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

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

When it happens

Trigger: Calling Delete on a tree whose nodes were manually mutated (writing to unexported fields via unsafe or reflection); calling DeleteIthKey directly to strip keys below the minimum; reusing nodes across trees with different maxKeys values.

Common situations: Mixing nodes between trees constructed with different maxKeys; external code poking at node internals in tests; a version mismatch where helper methods changed their invariants.

Related errors

• node has too many keys
• nodes should not have less than the minimum number of 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/17574f8d43ebf630. Report an issue: GitHub.