Full binary trees

A full binary tree is either a single node, or a root with exactly two full binary trees as its left and right subtrees.

A leaf has no children. Every other node is internal.

Structural induction proves a property of all such objects: prove it for the base case, then prove that building a bigger object from smaller ones keeps it true.