BST Property

A Binary Search Tree maintains a simple invariant: for every node with value $v$:

• All values in the left subtree are less than $v$
• All values in the right subtree are greater than $v$

Note: this applies to entire subtrees, not just immediate children.

If node 10 has left child 5, then 5's entire subtree must contain only values less than 10. This property enables binary search. To find value $x$:

$1.$ Compare $x$ with current node's value

$2.$ If equal, found it

$3.$ If $x$ is smaller, search left subtree

$4.$ If $x$ is larger, search right subtree Each comparison eliminates half the remaining tree (in the balanced case).