TheAlgorithms/Go · error

cannot merge when leaf node is parent

Error message

cannot merge when leaf node is parent

What it means

Merge combines children[idx] and children[idx+1] under the parent node by moving the parent's separator key down; a leaf has no children to merge, so the operation is meaningless and panics. Merge is only valid on an internal (non-leaf) node.

Source

Thrown at structure/tree/btree.go:221

	}
	node.numKeys--
}

// Transform:
//
//	A B C
//	 / \
//	a   b
//
// Into:
//
//	A C
//	 |
//
// a B c
func (node *BTreeNode[T]) Merge(idx int) {
	if node.isLeaf {
		panic("cannot merge when leaf node is parent")
	}
	left := node.children[idx]
	right := node.children[idx+1]
	left.Append(node.keys[idx], right.children[0])
	left.Concat(right, 0)
	node.DeleteIthKey(idx)
}

func (node *BTreeNode[T]) Min() T {
	if node.isLeaf {
		return node.keys[0]
	}
	return node.children[0].Min()
}

func (node *BTreeNode[T]) Max() T {
	if node.isLeaf {
		return node.keys[node.numKeys-1]

View on GitHub (pinned to 5ba447ec5f)

Solutions

1. Only call Merge on internal nodes — check !node.isLeaf first.
2. Use tree.Delete which only merges during internal-node rebalancing.
3. For underflowing leaves, borrow from a sibling or let the parent-level Delete logic handle it.

Example fix

// before
node.Merge(i) // node may be a leaf
// after
if !node.isLeaf {
    node.Merge(i)
}

if node.isLeaf {
    return errors.New("cannot merge a leaf node")
}
node.Merge(idx)

func safeMerge(n *BTreeNode[int], idx int) (err error) {
    defer func() {
        if r := recover(); r != nil { err = fmt.Errorf("merge failed: %v", r) }
    }()
    n.Merge(idx)
    return nil
}

When it happens

Trigger: Calling node.Merge(idx) directly on a leaf node; a custom Delete implementation that reaches a leaf before attempting rebalancing; calling Merge with a node from a tree where all nodes happen to be leaves (single-level tree).

Common situations: Implementing a custom delete/rebalance routine on top of the node API; tests invoking Merge on the root of a tree with no children.

Related errors

• BTree maxKeys cannot be zero
• Must be >= 3 keys
• node has too few keys
• node has too many keys
• Called InsertNonFull() with a full node

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