HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Relationship between height and depth of a binary tree

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
depthheightbetweenbinaryandtreerelationship

Problem

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

Solution

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

Code Snippets

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

Context

StackExchange Computer Science Q#63500, answer score: 3

Revisions (0)

No revisions yet.