# Properties of Full Binary Trees

## Prerequisites

### 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.

#### 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: • 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: 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`