# Number of leaf nodes in n-element red-black trees

Why the number of (NIL) leaf nodes in n-element red-black trees is n+1?

• This is tree for every full binary tree. – Yuval Filmus May 12 '18 at 8:56

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 ?