# Given a Red-Black Tree of n keys, is there a way to quickly determine if a red-node exists?

My best attempt at a specific case of the problem where $n =$ 256:

For a specific case that a RB tree has 256 nodes, we can use the RB tree theorem to deduce that the height of the tree $h \leq 2*lg(n+1)$ then $h\leq 16$ for $n =$ 256.

But this doesn't exactly help me deduce whether the last row is all black nodes (thereby implication the parent of these black nodes are red)

Can someone hep me carry this further?

• What do you mean by the "last row"? If you mean leafs then you can be sure they are all black (if it is a RB-tree this comes from the definition). Dec 16 '14 at 19:35
• @Byakuya Are you sure about that? I thought that leaves in RB trees can be any color, not just black. Dec 16 '14 at 20:27
• @templatetypedef You are not wrong. The colour of leaves depends on what you call leaves. If these are actually nodes holding a key, then they can be either red or black. Sometimes the nil-pointers at the bottom are considered leaves (I believe wikipedia does that) that obviously do not hold keys. Those leaves are considered black. Dec 16 '14 at 23:42
• If all nodes are black, then the tree is a perfectly balanced tree, which means it has $2^h-1$ keys for some $h$. The reverse is not true. When the tree has a power-of-two-minus-one nodes, it does not imply all these are black. Dec 16 '14 at 23:46