I'm currently cracking my brain over the following question: Prove that, in a red-black tree T, if every path from the root to a leaf contains at least one red node, then we can select a set of red nodes in T to color black such that T remains a valid red-black tree and the black-height increases by one.
Anyone has any tips on how to tackle this, I'm lost even starting
The easy way to think of it is by pushing red nodes up a tree and then turning the root black again.
Imagine a tree like the following:
B
R B
B B R B
B B B B B B R R
If there is a red node on every path then there will be at least one black node with two red children. If you push the red node up the tree at every position where this occurs, starting from the bottom eventually you will push the red node to the tree root at which point you can flip the color and the tree height has grown by one.
Also, if you ever reach a configuration where an entire level is red all the nodes at that level can be flipped without altering the tree properties and again the height has grown by one.
It is somewhat trickier if some paths have more than one red node, in that case you will want to work from the top-most red node in that path and push a red node from the other branch to match it.