Creating a Red-Black tree from BST tree - the fastest way?

Question

I have to create and describe an algorithm for my university course that gets a BST tree T and creates new BST tree T' that satifies properties (and is as fast as possible):
1) T' has the same exact key values as T
2) T' is a Red-Black tree

So far I've had only one idea: randomize 0 or 1. In case of 0, get the max key node from left subtree of T and insert it into T', otherwise get the min key node from right subtree of T and insert it into T'. This is to ensure that Red-Black tree is at least somewhat balanced. The insertion would be any standard RB insertion.
Complexity of getting min/max is O(h), and since this needs to be repeated for each of the nodes in T, this would get quite high. I could also keep a pointer at the max node of left subtree and min node of the right subtree, which would solve the problem of traversing the whole height of the tree every time.
What do you think about this solution? I'm pretty sure it can be done better. Sorry if there is an obvious better solution, but I couldn't find answer to this on the internet, also it's only my 2nd semester at the university and I don't have much experience with programming.

Answer 1

Unless you have some other constraints or information, the fastest way is to forget about the shape of the original BST.

Just put the keys in an ordered list, and build a complete binary tree from it, all in O(N) time.

Then, if there's a partially filled leaf level, then color those nodes red. The rest are black.