TheAlgorithms/Go · error

Called InsertNonFull() with a full node

Error message

Called InsertNonFull() with a full node

What it means

InsertNonFull must only be called on a node that is not full; the method checks IsFull first and panics if the node already holds maxKeys. It is an internal invariant — callers (the tree itself) are responsible for splitting full children before recursing.

Source

Thrown at structure/tree/btree.go:152

	// Reuse child as the left node
	child.numKeys = midKeyIndex

	// Insert the child's mid index to the parent
	for i := parent.numKeys; i > idx; i-- {
		parent.keys[i] = parent.keys[i-1]
		parent.children[i+1] = parent.children[i]
	}
	parent.keys[idx] = child.keys[midKeyIndex]
	parent.children[idx] = child
	parent.children[idx+1] = rightChild
	parent.numKeys += 1
}

func (node *BTreeNode[T]) InsertNonFull(tree *BTree[T], key T) {
	node.Verify(tree)
	if node.IsFull(tree.maxKeys) {
		panic("Called InsertNonFull() with a full node")
	}

	if node.isLeaf {
		// Node is a leaf. Directly insert the key.
		node.InsertKeyChild(key, nil)
		return
	}

	// Find the child node to insert into
	i := 0
	for ; i < node.numKeys; i++ {
		if key < node.keys[i] {
			break
		}
	}

	if node.children[i].IsFull(tree.maxKeys) {
		node.Split(i, tree.maxKeys)

View on GitHub (pinned to 5ba447ec5f)

Solutions

1. Call tree.Insert(key) instead of node.InsertNonFull directly — it handles root splitting.
2. If calling InsertNonFull on a child, check node.IsFull(tree.maxKeys) and call Split first.
3. Add a wrapper in your code that splits the root when full before recursing.

Example fix

// before
if tree.root.IsFull(tree.maxKeys) { /* forgot split */ }
tree.root.InsertNonFull(tree, key)
// after
tree.Insert(key)

if tree.root != nil && tree.root.IsFull(tree.maxKeys) {
    // split root first or just use tree.Insert
}
tree.Insert(key)

func safeInsertNonFull[T constraints.Ordered](n *BTreeNode[T], t *BTree[T], k T) (err error) {
    defer func() {
        if r := recover(); r != nil { err = fmt.Errorf("insert failed: %v", r) }
    }()
    if n.IsFull(t.maxKeys) { return errors.New("node full; split first") }
    n.InsertNonFull(t, k)
    return nil
}

When it happens

Trigger: Calling node.InsertNonFull(tree, key) directly on a node with numKeys == maxKeys without splitting first; misuse of the exported node-level API on the root when the tree should have split the root first.

Common situations: Custom insert loops in application code that call node methods instead of tree.Insert; tests reaching into internals; a new root created without the split being performed.

Related errors

• BTree maxKeys cannot be zero
• Must be >= 3 keys
• node has too few keys
• node has too many keys
• deleting out of bounds key

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