Properties of Full Binary Trees

Prerequisites

Trees Show

Binary Trees Show

Properties of Binary Trees Show

Properties of Full Binary Trees

Introduction

  • A full binary tree is a binary tree in which each node has exactly 0 or 2 child branches.
  • This article lists its various properties.

Notation

  • ni is the number of internal nodes.
  • ne is the number of external nodes.
  • ET is the external path length of tree T.
  • IT is the internal path length of tree T.

ni + 1 = ne

  • The number of internal nodes is one less than the number of external nodes.
  • Example: Example of a full binary tree with the nodes colored.
    • There are 2 (red) internal nodes.
    • There are 3 (blue) external nodes.
  • Proof:
    • For a tree with one node:
      ni = 0
ne = 1
    • Extending to a larger tree:
      • We can extend a tree by taking an external node and adding two branches to it.
      • This would convert the external node to an internal node:
        ni + 1
ne - 1
        And add two new external nodes:
        ne + 2
        This simplifies to:
        ni + 1
ne + 1
    • By induction, there is always 1 more external node.
  • This is identical to the n0 = n2 + 1 property of binary trees as:
    • ne = n0
    • ni = n2

ET = IT + 2ni

  • The external path length is equal to the internal path length + 2 * the number of internal nodes.
  • Example: example of a full binary tree
      In the above tree:
      • Internal path length (IT) = 1
      • External path length (ET) = 5
      • Internal nodes (ni) = 2
      • 5 = 1 + 2 * 2
  • Proof:
    • Proof using differential calculus
    • We can extend a tree by taking an external node k and adding two child branches to it
    • k changes from being an external node to an internal node
    • We label the change in the internal nodes (ni) as:
      ni dn
    • The internal path length (IT) will increase by the path length of k
    • We label this change, with respect to the change in ni as:
      IT dn
    • Similarly, the external path length will decrease by the same amount:
      ET dn = -IT dn
    • However, adding each of the two new external nodes will increase the external path length by the path length of k + 1
    • This now makes the change to the external path length:
      ET dn = -IT dn + 2(IT dn + 1)
    • Which simplifies to:
      ET dn = IT dn + 2
    • However we know that the increase in internal nodes is 1:
      ni dn = 1
    • Which we can substitute into our equation:
      ET dn = IT dn + 2ni dn
    • If we integrate this, with respect to dn then we get:
      ET = IT + 2ni + c
      where c is the constant of integration
    • Finally, if we examine the case where only the root node exists:
      • ni = 0
      • ET = 0
      • IT = 0
    • Then we also see that:
      • c = 0
    • If we remove c from our equation then:
      ET = IT + 2ni