Red Black Tree <Black Height> (Redraft)

Answer 1

As far as I can tell, you're checking black height only on the leftmost and rightmost paths down the tree. The definition of a red-black tree requires that black height be the same on all paths. For example, this invalid tree is not flagged by your program:

      B
     / \
    /   \
   /     \
  B       B
 / \     / \
B   R   R   B

Also, it doesn't check for cycles or if the keys are in order.