chap binary trees any number of internal nodes figure tree containing internal nodes and single leaf the full binary tree theorem some binary tree implementations store data only at the leaf nodesusing the internal nodes to provide structure to the tree more generallybinary tree implementations might require some amount of space for internal nodesand different amount for leaf nodes thusto analyze the space required by such implementationsit is useful to know the minimum and maximum fraction of the nodes that are leaves in tree containing internal nodes unfortunatelythis fraction is not fixed binary tree of internal nodes might have only one leaf this occurs when the internal nodes are arranged in chain ending in single leaf as shown in figure in this casethe number of leaves is low because each internal node has only one non-empty child to find an upper bound on the number of leaves for tree of internal nodesfirst note that the upper bound will occur when each internal node has two non-empty childrenthat iswhen the tree is full howeverthis observation does not tell what shape of tree will yield the highest percentage of non-empty leaves it turns out not to matterbecause all full binary trees with internal nodes have the same number of leaves this fact allows us to compute the space requirements for full binary tree implementation whose leaves require different amount of space from its internal nodes theorem full binary tree theoremthe number of leaves in non-empty full binary tree is one more than the number of internal nodes proofthe proof is by mathematical induction on nthe number of internal nodes this is an example of an induction proof where we reduce from an arbitrary instance of size to an instance of size that meets the induction hypothesis base casesthe non-empty tree with zero internal nodes has one leaf node full binary tree with one internal node has two leaf nodes thusthe base cases for and conform to the theorem induction hypothesisassume that any full binary tree containing internal nodes has leaves