What causes "Key "{key}" is not in the AVL tree." in TheAlgorithms/C-Sharp?

Check that the key exists before removing: call ContainsKey/Contains and only call Remove when it returns true.

TheAlgorithms/C-Sharp · error · KeyNotFoundException

Key " " is not in the AVL tree.

Error message

Key "{key}" is not in the AVL tree.

What it means

This KeyNotFoundException is thrown by the AVL tree's recursive Remove when the search descends past a null child, meaning the requested key does not exist in the tree. The library treats removal of an absent key as a programming error rather than a silent no-op, so it fails fast with the missing key in the message. Callers must ensure the key exists (e.g. via ContainsKey) or catch this exception.

Solutions

Check that the key exists before removing: call ContainsKey/Contains and only call Remove when it returns true.
Wrap the Remove call in try/catch (KeyNotFoundException) if absence is an expected, non-fatal condition.
Verify the same comparer (default vs custom) is used for every Insert/Remove/Search operation on the tree.
Log or validate the key source (user input, upstream data) to avoid deleting keys that were never added.

Example fix

// before
avlTree.Remove(userKey); // throws if userKey was never inserted

// after
if (avlTree.ContainsKey(userKey))
{
    avlTree.Remove(userKey);
}
else
{
    // handle absent key: log, return false, etc.
}

Defensive patterns

Strategy: try-catch

Validate before calling

// C#
if (!avlTree.ContainsKey(key))
{
    // skip removal or log; key is absent
}
else
{
    avlTree.Remove(key);
}

Type guard

// C#
static bool KeyExists<TK>(AVLTree<TK> tree, TK key) =>
    tree is not null && tree.ContainsKey(key);

Try / catch

// C#
try
{
    avlTree.Remove(key);
}
catch (KeyNotFoundException ex)
{
    // key absent — log ex.Message and continue
}

Prevention

Always gate Remove with ContainsKey when absence is possible.
Use the same comparer instance for insert and remove operations.
In drain loops, iterate while the tree reports non-empty rather than a fixed key count.
Treat Remove as throwing, not boolean-returning; never ignore the possibility of absence.

When it happens

Trigger: Calling AVLTree.Remove(key) (or the public Remove overload that delegates to the private Remove(node, key) at DataStructures/AVLTree/AVLTree.cs:380) with a key that was never inserted, or with a key that was already removed. Also occurs when a custom comparer orders keys differently from the one used at insertion time, so the search path misses the stored key.

Common situations: Removing an item twice in cleanup logic; deleting a key built from user input that never existed; switching or misconfiguring a custom comparer so lookups and insertions disagree; assuming Remove returned a success/failure indicator when it actually throws.

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

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

Appendix: source

Thrown at DataStructures/AVLTree/AVLTree.cs:380

        // Check all of the new node's ancestors for imbalance and perform
        // necessary rotations
        node.UpdateBalanceFactor();

        return Rebalance(node);
    }

    /// <summary>
    ///     Recursive function to remove node from tree.
    /// </summary>
    /// <param name="node">Node to check for key.</param>
    /// <param name="key">Key value to remove.</param>
    /// <returns>New node with key removed.</returns>
    private AvlTreeNode<TKey>? Remove(AvlTreeNode<TKey>? node, TKey key)
    {
        if (node == null)
        {
            throw new KeyNotFoundException(
                $"""Key "{key}" is not in the AVL tree.""");
        }

        // Normal binary search tree removal
        var compareResult = comparer.Compare(key, node.Key);
        if (compareResult < 0)
        {
            node.Left = Remove(node.Left, key);
        }
        else if (compareResult > 0)
        {
            node.Right = Remove(node.Right, key);
        }
        else
        {
            if (node.Left is null && node.Right is null)
            {
                return null;

View on GitHub (pinned to 96e2905cab)