
rooted ternary tree
A rooted ternary tree can be de ned by the following recursive de nition.
basis: The empty tree (containing no nodes) is a ternary tree.
inductive step: Create a root node r. Let T1; T2; T3 be three disjoint trees (i.e.
containing no nodes in common with r or one another). For each nonempty Ti,
connect r to Ti's root ri. r1; r2; r3 are called r's children.
A leaf is a node with no children. An internal node is a nonleaf node.
(a) The height of a tree is the maximum length of a path from the root to a leaf. The length
of a path is 1 less than the number of nodes it contains. What is the minimum height of
a ternary tree with ` leaves? Prove, using strong induction, that your answer is correct.
(b) A strict ternary tree is a ternary tree where each node has either exactly three children
or no children. Prove, using structural induction, that, in any nonempty strict ternary
tree, the number of leaves is equal to one plus twice the number of internal nodes. In
other words, if `(t) is the number of leaves in the tree t and k(t) is the number of internal
nodes, then `(t) = 2k(t) + 1.