Validate BST
Every node must sit inside a window inherited from all its ancestors, not just its parent.
Decision · step 2 of 5Build and Validate a BST: Swap two values and catch it
50 must be between open and open. It is. Its left child may be anything from open to 50, its right from 50 to open.
What you will see
Each node shows its allowed interval; a violation flashes.
Cost
| Best | O(n) |
|---|---|
| Average | O(n) |
| Worst | O(n) |
| Space | O(h) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, try operations in any order.
Screen readers: Nodes announce value, left child and right child; each step announces the comparison and the direction taken or the structural change.
Reduced motion: Focus jumps node to node with a static ring; rotations become a crossfade between the two layouts.
Before this
Taught by the same lesson
Build and Validate a BST covers these too, in the same run.