C1. It's not enough to use a BST with no modifications. You must at
least say that it's balanced or use a Red-Black or a 2-3 Tree.

C2. Just for future reference, if you say you're using Red-Black trees,
you can assume that you have use of all the operations RB-BSTs support.
So you can save some details there.

C3. Please describe what the key for the BST will be

C4. The question asks for an efficient implementation. O(n^2) is not it.

C5. Please be more complete. Proof by intimidation such as "it's
obvious..." and "By inspection..." cannot take you from assumptions to
conclusion in one step.