Full Binary Tree Theorem

 

The theorem

Let T be a nonempty, full binary tree.

The theorem claims that the number of nodes N, the number of leaves L, and the number of internal nodes I are related in such a way that if you know any one of them, you can determine the other two.

Specifically:

  1. If T has I internal nodes, the number of leaves is L = I + 1.
  2. If T has I internal nodes, the total number of nodes is N = 2I + 1.
  3. If T has a total of N nodes, the number of internal nodes is I = (N – 1)/2.
  4. If T has a total of N nodes, the number of leaves is L = (N + 1)/2.
  5. If T has L leaves, the total number of nodes is N = 2L – 1.
  6. If T has L leaves, the number of internal nodes is I = L – 1.

Here is a table that summarizes the above:

Internal Nodes  Leaves Nodes
 I  I + 1  2I+1
 2L – 1  L  L – 1
 (N – 1)/2.  (N + 1)/2  N

Other useful properties:

  • A tree with n nodes has n-1 edges
  • A tree with n nodes has height in the range of:

log2(n+1) <= h <= n

  • A full binary tree of a given height h has 2h – 1 nodes.
  • Let T be a binary tree with λ levels. Then T has no more than 2λ – 1 nodes
  • Let T be a binary tree with L leaves. Then the number of levels is at least
    ceil(logL) + 1 levels.
  • For a tree with height h, the number of nodes is in the range of:
h <= n <= 2h– 1

Here is a table that summarizes the above:

Height Nodes
log2(n+1) <= h <= n N
h h <= n <= 2h– 1

 

 

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s