Relationship between height and depth of a binary tree

Question

The wikipedia says that the number of nodes n in a full binary tree, is at least $n=2^h-1$ and at most $n=2^{h+1}-1$, where h is the height of the tree.

The following binary tree is full according to the wikipedia definition (every node has 0 or 2 children), n = 11, h = 4 but n is not greater than $2^4 - 1 = 15$.

Am I missing something?

                        .
                       /  \
                      a    .
                          / \      
                         b   .
                            / \
                           .   .
                          / \ / \
                         c  d e  f

Answer 1

You're not missing anything: it's a typo, which I've fixed. The page gives two separate definitions of "full binary tree" (a recursive one and the one you quote) and both of them include the following trees, which have even fewer nodes than yours ($2n-1$, to be precise):

  o
 / \
o   o
   / \
  o   .
       .
        .
         \
          o
         / \
        o   o

Answer 2

If you think about how you get these bounds¹ it's quite clear that they apply to complete binary trees, using terms from the article.

To be fair, the terminology around binary trees is ambiguous, overloaded, and inconsistent in the literature. It becomes worse if you use multiple languages. Hence, it comes to no surprise that a crowd-edited medium without real quality control such as Wikipedia would have errors.

---

1. Hint: $\sum 2^i$