In class, we defined afull binary treeto be first:binary, i.e. a tree where every node has at most two children, labelled asrightandleft; and second:full, meaning each node either has no children, or a full complement of two. Furthermore, we call nodes with no childrenleaves, and nodes with any childreninternal nodes. So, another way to define a full binary tree would be: "a binary tree where every internal node has exactly two children."

We can extend this to definefull ternary trees, which are trees where every node can have up to three children, and beingfull, every internal node hasexactly3 children.

Let intNodes(T) denote the number of internal nodes in a full ternary treeT, and let leaves(T) denote the number of leaves in that tree. Prove by induction that for all full ternary trees:

leaves(T) = 2 * intNodes(T) + 1