Think about a way of using the structure of the binary search tree itself to indicate color.