Number of leaf nodes in n-element red-black trees
By definition, a red-black tree is a full binary tree in which each node is assigned either red or black and the leaves are labeled as NIL-node while internal nodes are labeled as non-NIL node. In a full binary tree all of the nodes have either 0 or 2 children. Thus, assuming that a full binary tree has n internal nodes, the number of leaf nodes will be n + 1. So what you are asking is: if red-black tree has n non-NIL nodes why does it have n+1 NIL-nodes ?