How would I go about finding the percentage of red nodes in a red-black tree? I'm familiar with the properties of a red-black tree, but just can't seem to wrap my head around how to approach this. One idea I have is simply traversing the tree after building it and counting up the red nodes but it seems inefficient for larger inputs.
Well, you can trade time for space...
If you store the number of red and black nodes in each subtree, you can determine this only by looking at the root.
It is a property of red-black trees that information you store in the nodes which can be updated only by looking at a node's children (and possibly its parent; my memory is a bit hazy) doesn't affect the complexity of the tree operations.
So your tree building will be slower, but only by a constant factor.
Whether this factor is small enough that you save any time in practice if you only need to determine this percentage once is a different matter.