CODEWITHSUNDEEP
data-structuresbinary-treebinary-search-treeproofred-black-tree
sanic
sanic

Reputation: 2085

Can a red node have just 1 black child in a red-black tree?

The rules for a Red-Black Tree:

  1. Every node is either red or black.
  2. The root is black.
  3. Every leaf (NIL) is black.
  4. If a node is red, then both its children are black.
  5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

Rule 4 mentions that red nodes need both black childs but what if there is just one child to begin with? Is there an argument to prove or disprove this?

Upvotes: 4

Views: 3715

Answers (1)

Ehsaas
Ehsaas

Reputation: 41

No,a red node cannot have one child,consider the following cases:- 1.If the single child it has is red...this cannot happen because no two consecutive nodes can be red. 2.If the child is black...again this cannot happen because this would violate the 'Black Height Rule'...this case would give one extra black node in a path which is not correct according to the rule.

Upvotes: 4

Related Questions