Multiple choice

Which of the following statements is not true in context of red-black tree?

  1. A red–black tree is used to organize pieces of comparable data.

  2. All leaves (NIL) are black.

  3. Pre-order traversal of a red-black tree gives data in sorted order.

  4. Every red node must have two black child nodes.

  5. Red–black trees are particularly valuable in functional programming.
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

Red–black trees, like all binary search trees, allow efficient in-order traversal (that is: in the order Left–Root–Right) of their elements. The search-time results from the traversal from root to leaf, and therefore a balanced tree of n nodes, having the least possible tree height, results in O(log n) search time.

Keep practicing — related questions