23.1.2. Recurrence Relation for Full Binary Trees

Try these first

1. 1.

   What is a full binary tree?

   Hint

   Think about the structure of the nodes.

2. 2.

   Count the number of full binary trees for n=1.

   Hint

   Draw the tree structure.

3. 3.

   What is the defining property of a full binary tree?

   • Every node has 1 child
   • Every node has 0 or 2 children
   • Every node has at least 2 children

   Hint

   Think about the definition of internal nodes.

4. 4.

   True or False: The number of full binary trees can be counted using Catalan numbers.

   • True
   • False

   Hint

   Consider the connection we discussed recently.

5. 5.

   Design a full binary tree with n=4 and illustrate its distinct structures.

   Hint

   Try to structure your drawing step by step, ensuring every internal node follows the rules.

6. 6.

   Prove mathematically that the number of distinct full binary trees corresponds to the Catalan number.

   Hint

   You might use induction or combinatorial principles for demonstration!