{"record":{"id":"3c36d7623afd18b1","repo":"TheAlgorithms/C-Sharp","slug":"scapegoat-node-wasn-t-found-the-tree-should-be-unbalanced","errorCode":null,"errorMessage":"Scapegoat node wasn't found. The tree should be unbalanced.","messagePattern":"Scapegoat node wasn't found\\. The tree should be unbalanced\\.","errorType":"exception","errorClass":"InvalidOperationException","httpStatus":null,"severity":"error","filePath":"DataStructures/ScapegoatTree/ScapegoatTree.cs","lineNumber":266,"sourceCode":"    {\n        if (path.Count == 0)\n        {\n            throw new ArgumentException(\"The path collection should not be empty.\", nameof(path));\n        }\n\n        var depth = 1;\n\n        while (path.TryPop(out var next))\n        {\n            if (depth > next.GetAlphaHeight(Alpha))\n            {\n                return path.TryPop(out var parent) ? (parent, next) : (null, next);\n            }\n\n            depth++;\n        }\n\n        throw new InvalidOperationException(\"Scapegoat node wasn't found. The tree should be unbalanced.\");\n    }\n\n    private static void CheckAlpha(double alpha)\n    {\n        if (alpha is < 0.5 or > 1.0)\n        {\n            throw new ArgumentException(\"The alpha parameter's value should be in 0.5..1.0 range.\", nameof(alpha));\n        }\n    }\n\n    private bool Remove(Node<TKey>? parent, Node<TKey>? node, TKey key)\n    {\n        if (node is null || parent is null)\n        {\n            return false;\n        }\n\n        var compareResult = node.Key.CompareTo(key);","sourceCodeStart":248,"sourceCodeEnd":284,"githubUrl":"https://github.com/TheAlgorithms/C-Sharp/blob/96e2905cab7bc6b33ac0a34ee5bb82ddccbcbb6c/DataStructures/ScapegoatTree/ScapegoatTree.cs#L248-L284","documentation":"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.","triggerScenarios":"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.","commonSituations":"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.","solutions":["Verify the path stack passed corresponds to the actual most-recent insertion path.","Rebuild the tree (re-insert all keys) if internal counters or links were mutated externally.","Use a valid alpha in 0.5..1.0 and let Insert trigger rebalancing rather than calling internals manually."],"exampleFix":"// before\nvar (parent, scapegoat) = tree.FindScapegoatInPath(stalePath);\n// after\n// let Insert handle rebalancing instead of driving internals with a stale path\ntree.Insert(key);","handlingStrategy":"try-catch","validationCode":null,"typeGuard":null,"tryCatchPattern":"try { var (parent, scapegoat) = tree.FindScapegoatInPath(path); } catch (InvalidOperationException ex) { logger.LogError(ex, \"Scapegoat not found: tree state inconsistent\"); RebuildTree(); }","preventionTips":["Never mutate tree nodes or size counters directly.","Keep the path stack in sync with the actual last insertion.","Let Insert's automatic rebalancing drive scapegoat search."],"tags":["internal-state","trees","invariant-violation"],"backgroundTag":"internal-invariant-violation","analyzedSha":"96e2905cab7bc6b33ac0a34ee5bb82ddccbcbb6c","analyzedAt":"2026-09-13T17:04:01.438Z","contentChangedAt":"2026-09-13T17:04:01.438Z","schemaVersion":2},"datasetVersion":"2026-09-16T04:17:20.429Z"}