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

- n
_{i}is the number of internal nodes. - n
_{e}is the number of external nodes. - E
_{T}is the external path length of tree T. - I
_{T}is the internal path length of tree T.

#### n_{i} + 1 = n_{e}

- 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:
n

_{i}= 0 n_{e}= 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:
n

And add two new external nodes:_{i}+ 1 n_{e}- 1n

This simplifies to:_{e}+ 2n

_{i}+ 1 n_{e}+ 1

- By induction, there is always 1 more external node.

- For a tree with one node:
- This is identical to the n
_{0}= n_{2}+ 1 property of binary trees as:- n
_{e}= n_{0} - n
_{i}= n_{2}

- n

#### E_{T} = I_{T} + 2n_{i}

- The external path length is equal to the internal path length + 2 * the number of internal nodes.
- Example:
- Internal path length (I
_{T}) = 1 - External path length (E
_{T}) = 5 - Internal nodes (n
_{i}) = 2 - 5 = 1 + 2 * 2

In the above tree: - Internal path length (I
- 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 (n
_{i}) as:n

_{i}dn - The internal path length (I
_{T}) will increase by the path length of k - We label this change, with respect to the change in n
_{i}as:I

_{T}dn - Similarly, the external path length will decrease by the same amount:
E

_{T}dn = -I_{T}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:
E

_{T}dn = -I_{T}dn + 2(I_{T}dn + 1) - Which simplifies to:
E

_{T}dn = I_{T}dn + 2 - However we know that the increase in internal nodes is 1:
n

_{i}dn = 1 - Which we can substitute into our equation:
E

_{T}dn = I_{T}dn + 2n_{i}dn - If we integrate this, with respect to dn then we get:
E

where_{T}= I_{T}+ 2n_{i}+ c`c`is the constant of integration - Finally, if we examine the case where only the root node exists:
- n
_{i}= 0 - E
_{T}= 0 - I
_{T}= 0

- n
- Then we also see that:
- c = 0

- If we remove c from our equation then:
E

_{T}= I_{T}+ 2n_{i}