TheAlgorithms/C-Sharp · error · KeyNotFoundException

Key is not in the tree!

Error message

Key {key} is not in the tree!

What it means

RedBlackTree Remove(node, key) throws KeyNotFoundException when Contains(key) is false — the key is not present in a non-empty tree. The tree requires exact key existence before attempting rebalanced deletion.

Solutions

1. Check tree.Contains(key) before calling Remove.
2. Catch KeyNotFoundException when absence is an acceptable outcome.
3. Fix key construction/comparer so lookups match insertion (same normalization).
4. Track removed keys to avoid duplicate Remove calls.

Example fix

// before
tree.Remove(key); // KeyNotFoundException if absent
// after
if (tree.Contains(key))
{
    tree.Remove(key);
}

if (tree.Contains(key))
{
    tree.Remove(key);
}

try
{
    tree.Remove(key);
}
catch (KeyNotFoundException)
{
    // key absent — safe to ignore or log
}

When it happens

Trigger: Calling public Remove(key) with a key never added, or one already removed earlier, on a non-empty tree.

Common situations: Double-deletion in eviction logic, removing keys from a different tree instance than they were added to, comparer mismatches making keys non-equal, or stale key references after data reload.

Understand the failure class

Background: Record Not Found Errors: "not found", RecordNotFound, and "was not found" — what they mean and how to fix them — this error's family across 28 libraries.

Related errors

• key is not in the tree
• Tree is empty!
• Key " " already exists in tree!
• Tree is empty!
• Value is too big to fit into Int64

AI-assisted analysis of TheAlgorithms/C-Sharp@96e2905cab (2026-09-13). Data as JSON: /api/errors/fff7a84f3b0c1310. Report an issue: GitHub.

Appendix: source

Thrown at DataStructures/RedBlackTree/RedBlackTree.cs:453

            return 2;
        }
    }

    /// <summary>
    ///     Search for the node to be deleted.
    /// </summary>
    /// <param name="node">Node to start search from.</param>
    /// <param name="key">Key to search for.</param>
    /// <returns>Node to be deleted.</returns>
    private RedBlackTreeNode<TKey> Remove(RedBlackTreeNode<TKey>? node, TKey key)
    {
        if (node is null)
        {
            throw new InvalidOperationException("Tree is empty!");
        }
        else if (!Contains(key))
        {
            throw new KeyNotFoundException($"Key {key} is not in the tree!");
        }
        else
        {
            // Find node
            int dir;
            while (true)
            {
                dir = comparer.Compare(key, node!.Key);
                if (dir < 0)
                {
                    node = node.Left;
                }
                else if (dir > 0)
                {
                    node = node.Right;
                }
                else
                {

View on GitHub (pinned to 96e2905cab)