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)
A perfectly balanced tree of depth k has 2
UP>kUP> - 1 nodes.