Computer Science I / Debugging Structural Invariants
Practice question · Sort into groups

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

Groups: An invariant · Not an invariant

Hints
  1. An invariant must hold before and after EVERY operation, not merely right now.
  2. Ask of each statement whether an insertion could make it false without the structure being broken.
Show the 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.

Read the lesson: Debugging Structural Invariants →

Practise Debugging Structural Invariants

The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.

More questions on Debugging Structural Invariants