Q1) A binary tree is full if all of its vertices have either zero or two children. Let Bn denote the number of full binary trees with n vertices.
(a) By drawing out all full binary trees with 3, 5, and 7 vertices, determine the exact values of B3 , B5 , and B7 .
(b) Why have we left out full binary trees with even number of vertices, like B4, in part (a)?
(c) For general n, derive a recurrence relation for Bn .
(d) Show by induction (substitution) that Bn is 2 (n) .