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

BST Range Property

Generalize the invariant: each node's key must lie within a valid range inherited from ancestors.

BST Range Property

You'll learn how to generalize the BST invariant so that every node's key must fall within a valid range determined by its ancestors.

The Core Idea

You already know the basic BST invariant: left children are smaller, right children are larger. But here's the deeper insight: every node in a BST must satisfy range constraints inherited from all ancestors above it, not just its immediate parent.

When you go left from a node, you've set an upper bound for all descendants in that subtree. When you go right, you've set a lower bound. These constraints accumulate as you travel down the tree.

How Range Constraints Accumulate

Consider a root with key 50. Everything in the tree must be valid, but:

  • If you go left to 30, all nodes in that subtree must be < 50
  • If from 30 you go right to 40, that node must satisfy both < 50 (from root) and > 30 (from parent)
  • So 40 lives in the valid range (30, 50)

Think of it like descending through narrowing hallways: each decision point makes your available space smaller.

Why This Matters

This range property is crucial for:

  • Validating whether a binary tree is actually a BST
  • Understanding why simply checking parent-child pairs isn't enough
  • Implementing correct insertion and search operations

For example, this tree violates BST properties even though each parent-child pair looks okay locally:

    20
   /  \
  10   30
      /
     25  ← Invalid! Must be > 20 AND < 30 ✓, but what about > 10? Not checked!

Key Takeaway: Every node in a BST must respect a valid range (min, max) inherited from all ancestors along its path from the root, not just its immediate parent.