TheAlgorithms/C-Sharp · error · InvalidOperationException

Scapegoat node wasn't found. The tree should be unbalanced.

Error message

Scapegoat node wasn't found. The tree should be unbalanced.

What it means

FindScapegoatInPath scans the insertion path for a node violating the alpha weight-balance condition. If the entire path is traversed without finding one, the tree's balance state contradicts the reason rebalancing was triggered, so it throws InvalidOperationException. This signals a corrupted internal state rather than bad caller input.

Solutions

1. Verify the path stack passed corresponds to the actual most-recent insertion path.
2. Rebuild the tree (re-insert all keys) if internal counters or links were mutated externally.
3. Use a valid alpha in 0.5..1.0 and let Insert trigger rebalancing rather than calling internals manually.

Example fix

// before
var (parent, scapegoat) = tree.FindScapegoatInPath(stalePath);
// after
// let Insert handle rebalancing instead of driving internals with a stale path
tree.Insert(key);

try { var (parent, scapegoat) = tree.FindScapegoatInPath(path); } catch (InvalidOperationException ex) { logger.LogError(ex, "Scapegoat not found: tree state inconsistent"); RebuildTree(); }

When it happens

Trigger: Calling BalanceFromPath/FindScapegoatInPath when no node on the path actually violates the alpha balance condition — e.g. alpha was tuned after the imbalance existed, the path stack contents don't match the real tree, or size counters are out of sync.

Common situations: Custom code that mutates nodes or counts directly, mixing manual tree edits with the library's automatic rebalancing, or passing a path from a different tree/insertion.

Understand the failure class

Background: "This is a bug, please report it": internal invariant violations, unreachable panics, and SNH errors explained — this error's family across 47 libraries.

Related errors

• The parameter's value is invalid.
• The value's key is smaller than or equal to node's right…
• The value's key is greater than or equal to node's left…
• The path collection should not be empty.
• The alpha parameter's value should be in 0.5..1.0 range.

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

Appendix: source

Thrown at DataStructures/ScapegoatTree/ScapegoatTree.cs:266

    {
        if (path.Count == 0)
        {
            throw new ArgumentException("The path collection should not be empty.", nameof(path));
        }

        var depth = 1;

        while (path.TryPop(out var next))
        {
            if (depth > next.GetAlphaHeight(Alpha))
            {
                return path.TryPop(out var parent) ? (parent, next) : (null, next);
            }

            depth++;
        }

        throw new InvalidOperationException("Scapegoat node wasn't found. The tree should be unbalanced.");
    }

    private static void CheckAlpha(double alpha)
    {
        if (alpha is < 0.5 or > 1.0)
        {
            throw new ArgumentException("The alpha parameter's value should be in 0.5..1.0 range.", nameof(alpha));
        }
    }

    private bool Remove(Node<TKey>? parent, Node<TKey>? node, TKey key)
    {
        if (node is null || parent is null)
        {
            return false;
        }

        var compareResult = node.Key.CompareTo(key);

View on GitHub (pinned to 96e2905cab)