# Debugging Structural Invariants

Computer Science I · Data Structures · https://tryals.app/learn/computer-science-i/debugging-structural-invariants

## Catching Broken Rules

A **broken invariant** occurs when an operation leaves a data structure in a state its rules forbid. Make invariants explicit to catch bugs instantly.

| Structure | Core Invariant |
| --- | --- |
| **Binary Search Tree** | Left child < node < right child |
| **Heap** | Parent stands in correct order relation |
| **Doubly Linked List** | `a.next.prev == a` always holds |
| **Hash Table** | Every key resides in its hashed bucket |

Write a **checker**, a function that walks and verifies the structure after each operation. This applies the "fail fast" principle, catching corruption at the exact moment it happens.

## The Debugging Secret

A **checker** function stops you from hunting bugs downstream when reads finally return nonsense. Invariant checkers are cheap to write and double as executable documentation.

> **Common pitfall:** Debugging a data structure by inspecting only the **output** of operations. A corrupted structure often returns correct-looking results for a while before failing bizarrely.

Always check the **invariant** directly after each operation to instantly localize the bug to the exact code that broke your structure.

## Practice questions

5 of this lesson's 11 practice questions, with answers. The full set is in the app.

### 1. Order the steps of debugging a data structure with an invariant checker.

**Answer:**

1. Write down, in words, the property the structure must always satisfy
2. Write a function that walks the structure and verifies that property
3. Call the checker after every operation while reproducing the bug
4. Note the first operation after which the checker fails
5. Fix that operation, which is the one that corrupted the structure

**Why:** Stating the invariant, coding it, running it after every operation, and stopping at the first failure localises the bug to one operation. Without the checker you would find the damage far downstream, where the visible symptom has nothing to do with the code that caused it.

Page: https://tryals.app/practice/computer-science-i/debugging-structural-invariants/order-the-steps-of-debugging-a-data-structure-with-an-invariant

### 2. An invariant checker is written, run during development, and deleted before release. What was gained, and what was lost?

A. Gained speed in production, lost the ability to detect corruption in development
B. Nothing was lost, and the checker should never have been written
C. Bugs caught where they were caused, at no production cost
D. Nothing was gained, since the checker never ran in production

**Answer:** C. Bugs caught where they were caused, at no production cost

**Why:** The value is entirely in development, where it converts a distant symptom into an immediate one, so a released build loses nothing by omitting it. Compiling out rather than deleting keeps it available for the next change, which is exactly what assertion mechanisms are for.

Page: https://tryals.app/practice/computer-science-i/debugging-structural-invariants/an-invariant-checker-is-written-run-during-development-and-deleted

### 3. Sort each statement about a binary search tree by whether it is an invariant of the structure.

**Answer:**

- An invariant: Every value in a node's left subtree is less than the node's value, Every node except the root has exactly one parent, An in-order traversal yields the values in sorted order
- Not an invariant: The tree currently holds 12 values, The root currently holds the value 50

**Why:** The ordering property, the single-parent rule and the sorted traversal survive every legal operation, so they are invariants. The current size and the current root value change with a single insertion, so they describe this moment rather than a rule, and a checker that asserted them would fire constantly on a perfectly healthy tree.

Page: https://tryals.app/practice/computer-science-i/debugging-structural-invariants/sort-each-statement-about-a-binary-search-tree-by-whether-it-is-an

### 4. Select every benefit the lesson attributes to writing an invariant checker.

A. It localises a bug to the operation that broke the structure
B. It proves the structure's operations are as fast as claimed
C. It catches mis-linked pointers, unbalanced subtrees and mis-hashed keys
D. It removes the need to write any other tests
E. It documents what the structure guarantees, in executable form

**Answer:** A. It localises a bug to the operation that broke the structure; C. It catches mis-linked pointers, unbalanced subtrees and mis-hashed keys; E. It documents what the structure guarantees, in executable form

**Why:** Localisation, broad coverage of structural faults and executable documentation are all claimed. A checker says nothing about speed, and it verifies the structure's state rather than the results the program produces, so it complements other tests instead of replacing them.

Page: https://tryals.app/practice/computer-science-i/debugging-structural-invariants/select-every-benefit-the-lesson-attributes-to-writing-an-invariant

### 5. An invariant checker is code that verifies a structure's rules and is never called in production. Why is writing code you intend not to ship worth the effort?

A. Because production code cannot be tested by any other means.
B. Because it makes the structure faster by allowing optimisations that assume the invariant.
C. Because it converts a distant symptom into an immediate one.
D. Because invariant checkers can automatically repair the corruption they detect.

**Answer:** C. Because it converts a distant symptom into an immediate one.

**Why:** The value is in the distance between cause and symptom: a BST with one node on the wrong side does not crash, it quietly fails to find a present value thousands of operations later, in code that did nothing wrong. A checker turns that into an immediate local failure. It must detect and shout rather than repair, a checker that fixes what it finds destroys the evidence and leaves the bug.

Page: https://tryals.app/practice/computer-science-i/debugging-structural-invariants/an-invariant-checker-is-code-that-verifies-a-structures-rules-and-is