My data structures exam contains the following question:

Which of the statements below about red-black trees is true? (select one or more)

  1. Every path from the root to a leaf has the same amount of red links.
  2. A node never has two red links to his childs.
  3. Using a red-black tree, you can always draw the associated 2-3 tree.
  4. All leafs of a red-black tree are at the same height.

The correct answer is: 2 and 3.

I don't understand why a node can never have two red links to his child. On the image below (from Wikipedia), I can see two red childs at node 25.

Could someone explain this to me?

Red-black tree from Wikipedia


If 2 and 3 are both true, then the red-black trees you are sudying are not the standard ones, i.e., the ones from wikipedia.

The red nodes are usually assumed to be "satellites" of the black node above. If there is at most one red node attached to a black one that means either one or to keays belong together (with altogether either two or three pointers to their children). That nicely corresponds to a 2-3 tree.

The "usual" red-black trees can have two red children (but no red child to a red node) and correspond to 2-4 trees.

| cite | improve this answer | |
  • $\begingroup$ "(but no red child to a red node)" Maybe that's what they meant, but they didn't formulate it well. $\endgroup$ – Tijme Dec 13 '15 at 18:41
  • $\begingroup$ Well, if 3 is true, then they said exactly what they meant: one red node at most for a given black one. $\endgroup$ – Hendrik Jan Dec 13 '15 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.