Editor Staff asked 5 months ago
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.
Editor Staff answered 5 months ago
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.
