Next:Proof: Up:Aggregates Previous:Converting trees to lists

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~~UP>~~UP> - 1 nodes. *k*