TheAlgorithms/C-Sharp · error · InvalidOperationException

key is not in the tree

Error message

key is not in the tree

What it means

AATree.Remove(TKey key) first checks Contains(key, Root) and throws InvalidOperationException with message "key is not in the tree" if the key is absent. Removal of a non-existent key is treated as an invalid state for the caller rather than a silent no-op, so verify membership or catch the exception.

Solutions

1. Check tree.Contains(key) before calling Remove, or wrap Remove in try-catch on InvalidOperationException.
2. Ensure the same key values (and comparer semantics) used for insertion are used for removal.
3. Track removals to avoid deleting the same key twice (e.g. remove from a HashSet of pending keys).
4. If a no-op delete is desired, extend/wrap Remove to skip when the key is absent.

Example fix

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

if (!tree.Contains(key))
{
    return; // nothing to remove
}

try
{
    tree.Remove(key);
}
catch (InvalidOperationException ex) when (ex.Message.Contains("not in the tree"))
{
    // treat as no-op or log the unexpected removal
}

When it happens

Trigger: Calling tree.Remove(k) where k was never inserted or was already removed; removing with a key that is only equal under a different comparer than the tree's; calling Remove after Clear.

Common situations: Double-delete in test teardown (as in Remove_MultipleKeys_TreeStillValid / act test paths); keys sourced from a different collection that no longer exists in the tree; custom comparer mismatch making keys compare unequal.

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

• Tree is empty!
• Key is not in the tree!
• Value is too big to fit into Int64
• Value is too big to fit into Int32
• The sequence may only contain ones or zeros

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

Appendix: source

Thrown at DataStructures/AATree/AATree.cs:74

    /// <param name="keys">The elements to add to the tree.</param>
    public void AddRange(IEnumerable<TKey> keys)
    {
        foreach (var key in keys)
        {
            Root = Add(key, Root);
            Count++;
        }
    }

    /// <summary>
    ///     Remove a single element from the tree.
    /// </summary>
    /// <param name="key">Element to remove.</param>
    public void Remove(TKey key)
    {
        if (!Contains(key, Root))
        {
            throw new InvalidOperationException($"{nameof(key)} is not in the tree");
        }

        Root = Remove(key, Root);
        Count--;
    }

    /// <summary>
    ///     Checks if the specified element is in the tree.
    /// </summary>
    /// <param name="key">The element to look for.</param>
    /// <returns>true if the element is in the tree, false otherwise.</returns>
    public bool Contains(TKey key) => Contains(key, Root);

    /// <summary>
    ///     Gets the largest element in the tree. (ie. the element in the right most node).
    /// </summary>
    /// <returns>The largest element in the tree according to the stored comparer.</returns>
    /// <exception cref="InvalidOperationException">Thrown if the tree is empty.</exception>

View on GitHub (pinned to 96e2905cab)