Course contentsShow
← Computer Science
Lesson 494 of 2,87212. Binary Search TreesFree lesson

The BST Invariant

Formalize the BST property: for every node, all left descendants are smaller, all right descendants are larger.

The BST Invariant

What you'll learn: You'll understand the formal rule that makes a binary search tree "searchable" and distinguishes it from a regular binary tree.

The Core Rule

The BST invariant (also called the BST property) is the fundamental rule that every Binary Search Tree must satisfy at all times:

For every node in the tree, all values in its left subtree must be smaller than the node's value, and all values in its right subtree must be larger.

Notice we said "all left descendants," not just the immediate left child. This distinction matters! A node's left child might be smaller, but if that left child's right child is larger than the original node, the BST invariant is violated.

Why "Invariant"?

An invariant is a condition that always remains true. In a BST, no matter which node you examine, this property holds. It's not just about parent-child relationships—it's about entire subtrees.

Visualizing the Rule

Think of every node as a "gatekeeper" with a strict rule:

  • Everything to my left is smaller than me
  • Everything to my right is larger than me
  • This rule applies to my children, grandchildren, and all descendants

For example, if a node holds the value 50, then 30 can be in its left subtree, but so can 40, 25, and 10. Meanwhile, 70, 65, and 80 can all live in the right subtree. But 55 cannot appear anywhere in the left subtree, and 45 cannot appear in the right.

Key Takeaway: The BST invariant ensures that for every node, all left descendants < node < all right descendants—this property enables efficient searching and makes the tree "sorted" in structure.