The set of leaves and the set of internal nodes of a full binary tree (see page

Question

The set of leaves and the set of internal nodes of a full binary tree (see page 353 in the book) can be defined recursively.

Basis Step: The root r is a leaf of the full binary tree with exactly one node r. This tree has no internal nodes.

Recursive Step: The set of leaves of the tree T = Tleft ? Tright is the union of the leaves of Tleft and of Tright. The internal nodes of T are the root of T and the union of the internal nodes of Tleft and the set of the internal nodes of Tright.

Use structural induction to show that Leaf(T), the number of leaves of a full binary tree T, is 1 more than Internal(T), the number of internal nodes of T. That is, Leaf(T) = Internal(T) + 1.

Explanation / Answer

Proof. By induction on n.

T(n) := number of leaves in a non-empty, full tree of n internal nodes.

Base case: T(0) = 1 = n + 1.

Induction step: Assume T(i) = i + 1 for i < n.

Given T with n internal nodes, remove two sibling leaves.

T

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.