3
$\begingroup$

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
Improve this question
$\endgroup$
1
  • $\begingroup$ Ahhh, the joys of Wikipedia... $\endgroup$
    – Raphael ♦
    Sep 15, 2016 at 17:22

2 Answers 2

Reset to default
3
$\begingroup$

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
Improve this answer
$\endgroup$
4
  • $\begingroup$ this inductive proof math.stackexchange.com/a/220433/60114 seems to be ok and he proves that the minimum number of nodes is $2h + 1$ not $2h -1$. How did you arrive at that formula? $\endgroup$
    – dmz73
    Sep 16, 2016 at 9:03
  • $\begingroup$ @dmz73 I took the height to be the number of vertices on the longest path from leaf to root; the other answer probably took it to be the number of edges. $\endgroup$
    – David Richerby
    Sep 16, 2016 at 9:31
  • $\begingroup$ Since you edited wikipedia I think it would be better to consider depth as the number of edges, so that root is at level 0. This is the most common definition. $\endgroup$
    – dmz73
    Sep 16, 2016 at 23:52
  • $\begingroup$ @dmz73 "Wikipedia: the encyclopedia anyone can edit" (emphasis mine). $\endgroup$
    – David Richerby
    Sep 17, 2016 at 11:35
2
$\begingroup$

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$
Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Appropriately, the Wikipedia article even says that terminology is inconsistent. $\endgroup$
    – David Richerby
    Sep 15, 2016 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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