A complete binary tree is a graph defined through the following recur- sive definition. Basis step: A single vertex is a complete binary tree. Inductive step: If T1 and T2 are disjoint complete binary trees with roots r1, r2, respectively, the the graph formed by starting with a root r, and adding an edge from r to each of the vertices r1,r2 is also a complete binary tree. The set of leaves of a complete binary tree can also be defined recur- sively. Basis step: The root r is a leaf of the complete binary tree with exactly one vertex r. Inductive step: The set of leaves of the tree T built from trees T1, T2 is the union of the sets of leaves of T1 and the set of leaves of T2. The height h(T ) of a binary tree is defined in the class. Use structural induction to show that L(T), the number of leaves of a complete binary tree T , satisfies the following inequality L(T) ≤ 2^h(T).
A complete binary tree is a graph defined through the following recur- sive definition.
Basis step: A single vertex is a complete binary tree.
Inductive step: If T1 and T2 are disjoint complete binary trees with roots r1, r2, respectively, the the graph formed by starting with a root r, and adding an edge from r to each of the vertices r1,r2 is also a complete binary tree.
The set of leaves of a complete binary tree can also be defined recur- sively.
Basis step: The root r is a leaf of the complete binary tree with exactly one vertex r.
Inductive step: The set of leaves of the tree T built from trees T1, T2 is the union of the sets of leaves of T1 and the set of leaves of T2.
The height h(T ) of a binary tree is defined in the class.
Use structural induction to show that L(T), the number of leaves of a complete binary tree T , satisfies the following inequality
L(T) ≤ 2^h(T).
Trending now
This is a popular solution!
Step by step
Solved in 5 steps with 5 images
