# Exercise 13.3.5

Consider a red-black tree formed by inserting $n$ nodes with

`RB-INSERT`

. Argue that if $n > 1$, the tree has at least one red node.

The way `RB-INSERT`

is defined, it always introduces a new node colored red. The
only time it changes it's color to black is if it is the root, that is, if it's
a tree with 1 node. After we have a black root, each insert will color the newly
introduced element red and keep it red, regardless of how it rearranges the rest
of the tree.