The set of binary trees can be defined recursively as follows:

Basis Step: The empty tree () is a binary tree Recursive Step: For any binary tree T1 with root r1 and T2 with root r2, a new root r having T1 as its left subtree and T2 as its right subtree forms a binary tree.

Let the height of a tree be the number of nodes on the longest path from the root to a leaf. Use structural induction to prove that for any binary tree with n nodes and height h, n (2^h) 1.