In order to prove using structural induction some properties of functions which process trees we must first give an induction principle for the tree datatype. Such a principle can be derived directly from the definition of the datatype.
Induction Principle (Trees)
| (3) |
Proposition
A perfectly balanced tree of depth k has 2