Which of the following statement(s) is/are correct about red-black binary…
2021
Which of the following statement(s) is/are correct about red-black binary tree? Statements: I. Every node is either red or black. II. Every leaf node is red. III. When a node is red and both its children are black.
- A.
I and II
- B.
I, II and III
- C.
I and III
- D.
III and II
Attempted by 214 students.
Show answer & explanation
Correct answer: C
Red-black trees follow specific rules to maintain balance. Let's analyze each statement:
Statement I: Every node is either red or black. This is a fundamental property of red-black trees and is correct.
Statement II: Every leaf node is red. This is incorrect. In red-black trees, leaf nodes (NIL nodes) are always black to maintain balance and satisfy the black-height property.
Statement III: When a node is red, both its children are black. This is a core rule to prevent consecutive red nodes and ensure balance. The statement is correct in intent, though phrased incompletely.
Based on these properties, evaluate the options accordingly.