{"record":{"id":"6bbf6bc2e0276277","repo":"stanfordnlp/CoreNLP","slug":"node-size-is-not-one-plus-the-sum-of-left-and-righ","errorCode":null,"errorMessage":"node size is not one plus the sum of left and right!!!","messagePattern":"node size is not one plus the sum of left and right!!!","errorType":"exception","errorClass":"IllegalStateException","httpStatus":null,"severity":"error","filePath":"src/edu/stanford/nlp/util/IntervalTree.java","lineNumber":381,"sourceCode":"        if (node.right != null) throw new IllegalStateException(\"Empty node shouldn't have right branch\");\n        continue;\n      }\n      int leftSize = (node.left != null)? node.left.size:0;\n      int rightSize = (node.right != null)? node.right.size:0;\n      E leftMax = (node.left != null)? node.left.maxEnd:null;\n      E rightMax = (node.right != null)? node.right.maxEnd:null;\n      E maxEnd = node.value.getInterval().getEnd();\n      if (leftMax != null && leftMax.compareTo(maxEnd) > 0) {\n        maxEnd = leftMax;\n      }\n      if (rightMax != null && rightMax.compareTo(maxEnd) > 0) {\n        maxEnd = rightMax;\n      }\n      if (!maxEnd.equals(node.maxEnd)) {\n        throw new IllegalStateException(\"max end is not as expected!!!\");\n      }\n      if (node.size != leftSize + rightSize + 1) {\n        throw new IllegalStateException(\"node size is not one plus the sum of left and right!!!\");\n      }\n      if (node.left != null) {\n        if (node.left.parent != node) {\n          throw new IllegalStateException(\"node left parent is not same as node!!!\");\n        }\n      }\n      if (node.right != null) {\n        if (node.right.parent != node) {\n          throw new IllegalStateException(\"node right parent is not same as node!!!\");\n        }\n      }\n      if (node.parent != null) {\n        // Go up parent and make sure we are on correct side\n        TreeNode<E,T> n = node;\n        while (n != null && n.parent != null) {\n          // Check we are either right or left\n          if (n == n.parent.left) {\n            // Check that node is less than the parent","sourceCodeStart":363,"sourceCodeEnd":399,"githubUrl":"https://github.com/stanfordnlp/CoreNLP/blob/1b7edd19c4d0d7b1f13a2591425b9b60a0b1af7a/src/edu/stanford/nlp/util/IntervalTree.java#L363-L399","documentation":"TreeNode caches subtree size to support balancing and ranking. check() asserts node.size == leftSize + rightSize + 1 and throws this IllegalStateException when the cached count diverges from the actual subtree. This means size counters were not maintained through some insert/remove/rotation path — internal corruption of the tree.","triggerScenarios":"check() (directly or via balance()/rotateUp()) computes leftSize/rightSize from children and finds node.size differs from their sum plus one — typically after a rotation that forgot to recompute sizes or a remove() that decremented the wrong path.","commonSituations":"Hit while debugging insert/remove-heavy usage of CoreNLP's IntervalTree; after concurrent unsynchronized mutation; after code that bypassed the public API and edited node fields directly.","solutions":["Rebuild the IntervalTree (fresh instance, re-insert all intervals) to reset all size fields.","Only mutate through insert()/remove(); never adjust node.size or child pointers manually.","Restrict the tree to one thread or add external synchronization — no internal locking exists.","Capture the minimal public-API sequence that corrupts the size and file a CoreNLP bug."],"exampleFix":null,"handlingStrategy":"validation","validationCode":"// Cheap post-mutation invariant check\ntry { tree.check(tree.root); } catch (IllegalStateException e) { corrupt = true; }","typeGuard":null,"tryCatchPattern":"try {\n  tree.remove(iv, val);\n  tree.check(tree.root); // dev/test builds only\n} catch (IllegalStateException e) {\n  tree = rebuildTree(intervals);\n}","preventionTips":["Only mutate through insert()/remove(); size fields are maintained internally.","Avoid unsynchronized concurrent updates which can desynchronize size counters.","Rebuild the tree after very large numbers of removals if stability is uncertain.","Enable check() in test suites over randomized insert/remove sequences."],"tags":["interval-tree","invariant","size-accounting","corenlp"],"backgroundTag":"internal-invariant-violation","analyzedSha":"1b7edd19c4d0d7b1f13a2591425b9b60a0b1af7a","analyzedAt":"2026-09-10T02:24:07.274Z","contentChangedAt":"2026-09-10T02:24:07.274Z","schemaVersion":2},"datasetVersion":"2026-09-17T15:17:12.973Z"}