Solution Found!
The set of leaves and the set of internal vertices of a
Chapter 5, Problem 44E(choose chapter or problem)
The set of leaves and the set of internal vertices of a full binary tree can be defined recursively.
Basis step: The root r is a leaf of the full binary tree with exactly one vertex r. This tree has no internal vertices.
Recursive step: The set of leaves of the tree \(T=T_{1} \cdot T_{2}\) is the union of the sets of leaves of \(T_{1}\) and of \(T_{2}\).The internal vertices of T are the root r of T and the union of the set of internal vertices of \(T_{1}\) and the set of internal vertices of \(T_{2}\).
Use structural induction to show that \(l(T)\), the number of leaves of a full binary tree T, is 1 more than \(i(T)\), the number of internal vertices of T.
Questions & Answers
QUESTION:
The set of leaves and the set of internal vertices of a full binary tree can be defined recursively.
Basis step: The root r is a leaf of the full binary tree with exactly one vertex r. This tree has no internal vertices.
Recursive step: The set of leaves of the tree \(T=T_{1} \cdot T_{2}\) is the union of the sets of leaves of \(T_{1}\) and of \(T_{2}\).The internal vertices of T are the root r of T and the union of the set of internal vertices of \(T_{1}\) and the set of internal vertices of \(T_{2}\).
Use structural induction to show that \(l(T)\), the number of leaves of a full binary tree T, is 1 more than \(i(T)\), the number of internal vertices of T.
ANSWER:Step 1 of 3
We are given that
\(l(T)\) is the number of leaves of a full binary tree
\(i(T)\) is the number of internal vertices of T
We have to prove \(l(T)=i(T)+1\).