Maximum number of red nodes in red black tree

Question

In a red-black tree with n nodes, what is the maximum number of red nodes (assuming the root is black)?

Is it O(n)?

Answer 1

If the tree has n nodes and the root is black, there are n - 1 nodes left and n - 1 = O(n), so you're right.

If you want to count/bound number of red nodes in the tree more accurately, you have to know the topology of that tree.

For instance, if the tree is a complete binary tree, according to the definition of the red-black-tree, it can have no red nodes at all.