23.1.1. Full Binary Tree Definition

Try these first

1. 1.

   What is a full binary tree?

   Hint

   Think about the number of children each node can have.

2. 2.

   How many leaves does H(1) represent?

   Hint

   Consider that leaves are the endpoints without children.

3. 3.

   What defines a full binary tree?

   • Every node has exactly one child.
   • Every internal node has zero or two children.
   • It has a maximum of three children per node.

   Hint

   Focus on understanding the basic properties of tree structures.

4. 4.

   Is H(1) greater than H(2)?

   • True
   • False

   Hint

   Recall the number of leaves corresponding to each H value.

5. 5.

   Create and illustrate a full binary tree with 5 leaves. Explain the process of constructing this tree.

   Hint

   Remember to add pairs of nodes while ensuring the total is odd for leaves.

6. 6.

   Derive the nth Catalan number using the formula and relate it to the number of full binary trees.

   Hint

   Recall the combinatorial interpretations of Catalan numbers!