Some Properties of Binary Search Trees

Height is O(n) (imbalanced) and $\Omega(\log n)$ (balanced).

Where are largest and smallest elements?

In what sense does each position in the tree represent a range?


next up previous
Next: Finding a Key Up: BINARY SEARCH TREES Previous: Binary-Search-Tree Definition