AlgoScope

Validate BST

Every node must sit inside a window inherited from all its ancestors, not just its parent.

Tree algorithms, algorithm, intermediate
50 must lie between open and open. It does.60304050207080current
50 must lie between open and open. It does.60304050207080current

Build and Validate a BST: Swap two values and catch it

Decision, step 2 of 5

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.

How build and validate a bst works

Cost

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(h)

Leads to

Topics that need this one first.

Taught by the same lesson

Build and Validate a BST covers these too, in the same run.