TheAlgorithms/Java · error · EmptyTreeException

Cannot delete from an empty tree

Error message

Cannot delete from an empty tree

What it means

SplayTree.delete(int key) guards against operating on an empty tree by calling isEmpty() (root == null) at entry. Deleting from a tree with no nodes is a logic error — there is nothing to remove or splay — so it throws EmptyTreeException (a RuntimeException subclass) with a descriptive message.

Source

Thrown at src/main/java/com/thealgorithms/datastructures/trees/SplayTree.java:72

     * Search for a key in the SplayTree.
     *
     * @param key The key to search for.
     * @return True if the key is found, otherwise false.
     */
    public boolean search(int key) {
        root = splay(root, key);
        return root != null && root.key == key;
    }

    /**
     * Deletes a key from the SplayTree.
     *
     * @param key The key to delete.
     * @throws IllegalArgumentException If the tree is empty.
     */
    public void delete(final int key) {
        if (isEmpty()) {
            throw new EmptyTreeException("Cannot delete from an empty tree");
        }

        root = splay(root, key);

        if (root.key != key) {
            return;
        }

        if (root.left == null) {
            root = root.right;
        } else {
            Node temp = root;
            root = splay(root.left, findMax(root.left).key);
            root.right = temp.right;
        }
    }

    /**

View on GitHub (pinned to fdfb9a395b)

Solutions

  1. Check !tree.isEmpty() before calling delete.
  2. Maintain an element count alongside the tree and guard delete when count reaches zero.
  3. Catch EmptyTreeException if the caller treats delete-on-empty as a no-op.

Example fix

// before
tree.delete(42); // throws if tree is empty

// after
if (!tree.isEmpty()) {
    tree.delete(42);
}
Defensive patterns

Strategy: validation

Validate before calling

if (!tree.isEmpty()) {
    tree.delete(key);
}

Try / catch

try {
    tree.delete(key);
} catch (SplayTree.EmptyTreeException e) {
    // no-op: tree is already empty, nothing to delete
}

Prevention

When it happens

Trigger: Calling delete(key) on a newly constructed SplayTree before any insert, or after all nodes have been deleted in a prior sequence of operations.

Common situations: Batch processing pipelines that delete keys from a shared tree without tracking whether it has been emptied; test teardown that deletes keys one-by-one and hits the last deletion edge case.

Related errors

AI-assisted analysis of TheAlgorithms/Java@fdfb9a395b (2026-08-13). Data as JSON: /api/errors/248489dfd222dfa9. Report an issue: GitHub.