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

Valid vs Invalid BSTs

Identify valid and invalid BST examples; recognize common mistakes in BST construction.

Valid vs Invalid BSTs

You'll learn how to spot the difference between legitimate Binary Search Trees and imposters that break the rules.

The Core Rule Revisited

A Binary Search Tree must follow one strict rule everywhere: for every node, all values in its left subtree must be smaller, and all values in its right subtree must be larger. The tricky part? This isn't just about immediate children—it applies to every descendant node.

Common Mistake: The Local-Only Check

The biggest BST construction error is checking only a node's direct children while ignoring deeper descendants.

Invalid Example:

    10
   /  \
  5    15
      /  \
     12   20
    /
   13

Looking quickly, this seems fine—15 > 10, and 12 < 15. But notice that 13 is in the right subtree of 10, yet 13 > 10 AND 13 < 15. The node containing 13 belongs in 10's right subtree (correct), but it also belongs in 15's left subtree (also correct locally). However, the path violates no rules—this is actually valid! Let me show a truly broken one:

Truly Invalid Example:

    10
   /  \
  5    15
      /  \
     6    20

Here, 6 is in node 10's right subtree but 6 < 10—this breaks the BST property. Even though 6 < 15 (correct locally), the global constraint fails.

Valid Example

    10
   /  \
  5    15
 / \   / \
3   7 12  20

Every node respects the property both locally and globally.

Key Takeaway: A valid BST satisfies the ordering property at every node considering all descendants, not just immediate children. Always verify that values respect bounds inherited from ancestor nodes.