# Number of nil-links in a binary tree

In its section Properties of binary trees Wikipedia states:

The maximum possible number of null links (i.e., absent children of the nodes) in a complete binary tree of n nodes is (n+1), where only 1 node exists in bottom-most level to the far left.

I wonder about the precise statement used here. In my opinion every binary tree with $$n$$ nodes has exactly $$n+1$$ nil links (or missing children). A proof by induction is easy. (In fact that is equivalent to the statement some lines above: "a perfect binary tree with $$\ell$$ leaves has $$n=2\ell-1$$ nodes".)

Question: what am I missing here? Has Wikipedia different assumptions on binary trees?

As an illustration, a non-complete binary tree with 12 nodes and 13 nil-pointers, marked as square nodes. It can also been seen as a perfect binary tree with 25 nodes, the squares indicating leafs.

• The Wikipedia article is probably assuming leaves (i.e., the nodes in the last level of the tree) do not have links. Hence, to determine the number of null links you only look at the previous to last level of the tree. This also explains the maximum case (i.e., "where only 1 node exists in bottom-most level"). – dkaeae May 28 '19 at 12:31
• @dkaeae Make your comment an answer? It explains both issues indeed. – Hendrik Jan May 28 '19 at 12:39
• Glad to be of help. Refined and posted :) – dkaeae May 28 '19 at 12:57