What causes "Duplicate key: {key}" in TheAlgorithms/Java?

Call tree.search(key) first and skip insertion if it returns true.

TheAlgorithms/Java · error · DuplicateKeyException

Duplicate key: {key}

Error message

Duplicate key: {key}

What it means

SplayTree does not allow duplicate keys. insertRec(Node, int) traverses the BST and, when it encounters a node whose key equals the key being inserted, throws DuplicateKeyException (a RuntimeException subclass) with the offending key in the message. This enforces set semantics for the tree.

Source

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

            } else if (root.right.key < key) {
                root.right.right = splay(root.right.right, key);
                root = rotateLeft(root);
            }
            return (root.right == null) ? root : rotateLeft(root);
        }
    }

    private Node insertRec(Node root, final int key) {
        if (root == null) {
            return new Node(key);
        }

        if (key < root.key) {
            root.left = insertRec(root.left, key);
        } else if (key > root.key) {
            root.right = insertRec(root.right, key);
        } else {
            throw new DuplicateKeyException("Duplicate key: " + key);
        }

        return root;
    }

    public static class EmptyTreeException extends RuntimeException {
        private static final long serialVersionUID = 1L;

        public EmptyTreeException(String message) {
            super(message);
        }
    }

    public static class DuplicateKeyException extends RuntimeException {
        private static final long serialVersionUID = 1L;

        public DuplicateKeyException(String message) {
            super(message);

View on GitHub (pinned to fdfb9a395b)

Solutions

Call tree.search(key) first and skip insertion if it returns true.
Catch DuplicateKeyException at the call site if duplicates are acceptable and should be silently ignored.
Deduplicate your input collection before inserting into the tree.

Example fix

// before
tree.insert(10);
tree.insert(10); // throws DuplicateKeyException

// after
tree.insert(10);
if (!tree.search(10)) {
    tree.insert(10);
}

Defensive patterns

Strategy: validation

Validate before calling

if (!tree.search(key)) {
    tree.insert(key);
}

Try / catch

try {
    tree.insert(key);
} catch (SplayTree.DuplicateKeyException e) {
    // key already present — treat as no-op or update
}

Prevention

Deduplicate input data before inserting into the tree.
Always check search(key) before insert if duplicates are possible.

When it happens

Trigger: Calling tree.insert(key) when a node with that exact key already exists in the tree — including re-inserting after a prior successful insert of the same value.

Common situations: Ingesting data from a source with non-unique identifiers; retry/replay logic that re-inserts keys; concurrent-feeling code paths where two callers insert the same key.

Related errors

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