Question

What is the special property of red-black trees and what root should always be?

(a) a color which is either red or black and root should always be black color only

(b) height of the tree

(c) pointer to next node

(d) a color which is either green or black

I'm obligated to ask this question of Red Black Tree in chapter Binary Trees of Data Structures & Algorithms I

The question was asked in a job interview.

Answer 1

Right option is (a) a color which is either red or black and root should always be black color only

The best explanation: An extra attribute which is a color red or black is used. root is black because if it is red then one of red-black tree property which states that number of black nodes from root to null nodes must be same, will be violated.