Binary-Search-Tree Definition

An n-node binary tree.

Not necessarily complete.

All nodes j (other than leaves) satisfy the ``binary-search-tree property'': $\mbox{key}(i) \le \mbox{key}(j) \le \mbox{key}(k)$.Here, i is in j's left subtree, and k is j's right subtree.

In terms of the array representation: $T_v[i] \le T_v[j] \le T_v[k]$.

Example... Note: not enough that the property just holds for immediate children. Must hold for the entire family line.