Question: If a Red-Black tree has greater than 1 node, it is guaranteed to have at least 1 red node...why?
I am currently in the field and working on my Masters degree in CS. This is a question I encountered and could not verify the answer to. From the research I have done, this is what I have come up with:
When you insert the root, it is initially red, but recolored to black (rule: root must be black). After this, the next node will be inserted to the left or right, it will be colored red. After this, there is no case of re-coloring or rotation that will reduce the number of red nodes to zero.
Any verification/help would be much appreciated.
Thank you in advance.
Add your 2¢