1
$\begingroup$

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.

a binary tree, not complete, with nil-pointers marked

$\endgroup$
  • 1
    $\begingroup$ 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"). $\endgroup$ – dkaeae May 28 at 12:31
  • $\begingroup$ @dkaeae Make your comment an answer? It explains both issues indeed. $\endgroup$ – Hendrik Jan May 28 at 12:39
  • $\begingroup$ Glad to be of help. Refined and posted :) $\endgroup$ – dkaeae May 28 at 12:57
2
$\begingroup$

The Wikipedia article defines a null links as "absent children of the nodes", presumably "absent" in the sense of what nodes are missing to obtain a perfect binary tree (i.e., "a binary tree in which all interior nodes have two children and all leaves have the same depth or same level"). Under this definition, leaves (i.e., the nodes in the last level of the tree) do not have links. Hence, because all other levels are filled, to determine the number of null links you need 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")

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.