12-06-2018, 02:00 AM

Exam question (abbreviated):

Suppose you allowed, at most, two red nodes in a row on any path from an interior node to a leaf in a RBT. Suppose further, a path from the root to a leaf has 11 black nodes. What is the most number of red leaves that can appear on that path?

Can anyone explain the idea we are trying to understand here? Also how would one set this up when solving the problem?

Suppose you allowed, at most, two red nodes in a row on any path from an interior node to a leaf in a RBT. Suppose further, a path from the root to a leaf has 11 black nodes. What is the most number of red leaves that can appear on that path?

Can anyone explain the idea we are trying to understand here? Also how would one set this up when solving the problem?