What color must every leaf (NIL) be in a valid Red-Black Tree?
Show answer
Black
By definition, the NIL leaves of a Red-Black Tree are considered black. This property helps simplify the tree rotation and re-coloring logic used during insertions and deletions.