9.1 Answer the questions below about the following binary tree:
a. What is the root element?
b. How many elements are in the tree?
c. How many leaves are in the tree?
d. What is the height of the tree?
e. What is the height of the left subtree?
f. What is the height of the right subtree?
g. What is the level of F?
h. What is the depth of C?
i. How many children does C have?
j. What is the parent of F?
k. What are the descendants of B?
l. What are the ancestors of F?
m. What would the output be if the elements were written out during an inOrder traversal?
n. What would the output be if the elements were written out during a postOrder traversal?
o. What would the output be if the elements were written out during a preOrder traversal?
p. What would the output be if the elements were written out during a breadth-first traversal? Get the solution of 9.1
9.2 a. Construct a binary tree of height 3 that has 8 elements.
b. Can you construct a binary tree of height 2 that has 8 elements?
c. For n going from 1 to 20, determine the minimum height possible for a binary tree with n elements.
d. Based on your calculations in part c, try to develop a formula for the minimum height possible for a binary tree with n elements, where n can be any positive integer.
e. Use the Principle of Mathematical Induction (Strong Form) to prove the correctness of your formula in part d. Get the solution of 9.2
9.3 a. What is the maximum number of leaves possible in a binary tree with 10 elements? Construct such a tree.
b. What is the minimum number of leaves possible in a binary tree with 10 elements? Construct such
a tree. Get the solution of 9.3
9.4 a. Construct a two-tree that is not complete.
b. Construct a complete tree that is not a two-tree.
c. Construct a complete two-tree that is not full.
d. How many leaves are there in a two-tree with 17 elements?
e. How many leaves are there in a two-tree with 731 elements?
f. A non-empty two-tree must always have an odd number of elements. Why?
Hint: Use the Binary Tree Theorem and the fact that the number of leaves must be an integer.
g. How many elements are there in a full binary tree of height 4?
h. How many elements are there in a full binary tree of height 12?
i. Use induction (original form) on the height of the tree to show that any full binary tree is a two tree.
j. Use the results from part i and the Binary Tree Theorem to determine the number of leaves in a full binary tree with 63 elements.
k. Construct a complete two-tree that is not full, but in which the heights of the left and right subtrees are equal. Get the solution of 9.4
9.5 For the following binary tree, show the order in which elements would be visited for an inOrder, postOrder, preOrder, and breadthFirst traversal.
9.7 Show that if t is a complete binary tree, then
height(t ) = floor(log2(n(t )))
Hint: Let t be a complete binary tree of height k ≥ 0, and let t1 be a full binary tree of height k − 1. Then n(t1) + 1 ≤ n(t ). Use Part 4 of the Binary Tree Theorem to show that floor(log2 (n(t1) + 1)) = k, and use Part 1 of the Binary Tree Theorem to show that floor(log2(n(t ))) < k + 1. Get the solution of 9.7
9.8 The Binary Tree Theorem is stated for non-empty binary trees. Show that parts 1, 2, and 4 hold even for an empty binary tree. Get the solution of 9.8
9.9 Give an example of a non-empty binary tree that is not a two-tree but
leaves(t) = (n(t) + 1) / 2
Hint: The denominator is 2, not 2.0, so integer division is performed. Get the solution of 9.9
9.10 Let t be a non-empty tree. Show that if
leaves(t ) = n(t ) + 1 / 2.0
then either both subtrees of t are empty or both subtrees of t are non-empty.
Note: Do not use Part 3 of the Binary Tree Theorem. This exercise can be used in the proof of Part 3. Get the solution of 9.10
9.11 Show that in any complete binary tree t, at least half of the elements are leaves.
Hint: if t is empty, there are no elements, so the claim is vacuously true. If the leaf at the highest index is a right child, then t is a two-tree, and the claim follows from part 3 of the Binary Tree Theorem. Otherwise, t was formed by adding a left child to the complete two-tree with n(t ) − 1 elements. Get the solution of 9.11
9.12 Compare the inOrder traversal algorithm in Section 9.5 with the move method from the Towers of Hanoi application in Section 5.4 of Chapter 5. They have the same structure, but worstTime(n) is linear in n for the inOrder algorithm and exponential in n for the move method. Explain. Get the solution of 9.12
9.13 Let t be a nonempty binary tree. Use the Strong Form of the Principle of Mathematical Induction to prove each of the following parts of the Binary Tree Theorem:
a.
n(t ) + 1
2.0 ≤ 2height(t )
b. If t is a two-tree, then leaves(t ) = n(t ) + 1 / 2.0
c. If t is a full tree, then
n(t ) + 1 / 2.0 = 2height(t )
Hint: The outline of the proof is the same as in Example A2.5 of Appendix 2. Get the solution of 9.13
9.14 Let t be a nonempty binary tree. Use the Strong Form of the Principle of Mathematical Induction to prove each of the following parts of the Binary Tree Theorem:
a. If leaves(t ) = n(t ) + 1 / 2.0
then t is a two-tree.
b. If
n(t ) + 1
2.0 = 2height(t ) then t is a full tree.
Hint: The proof for both parts has the same outline. For example, here is the outline for part a:
For h = 0, 1, 2, . . . , let Sh be the statement
If t is a binary tree of height h and leaves(t ) = n(t ) + 1 / 2.0
then t is a two-tree.
In the inductive case, let h be any nonnegative integer and assume that S0, S1, . . ., Sh are all true. To show that Sh+1 is true, let t be a binary tree of height h + 1 such that
leaves(t ) = n(t ) + 1 / 2.0
First, show that
leaves(leftTree(t )) + leaves(rightTree(t )) = n(leftTree(t )) + 1 / 2.0 + n(rightTree(t )) + 1 / 2.0
For any non-negative integers a, b, c, and d, if
a + b = c + d and a ≤ c and b ≥ d, then a = c and b = d.
Then, using Exercise 8.10, show that leftTree(t) and rightTree(t) are two-trees. Then, using Exercise
8.8, show that both leftTree(t) and rightTree(t) are nonempty. Conclude, from the definition of a two-tree, that t must be a two-tree. Get the solution of 9.14
9.15 For any positive integer n, we can construct a binary tree of n elements as follows:
at level 0, there will be 1 element (the root);
at level 1, there will be 2 elements;
at level 2, there will be 3 elements;
at level 3, there will be 4 elements;
at level 4, there will be 5 elements;
. . .
At the level farthest from the root, there will be just enough elements so the entire tree will have n elements.
For example, if n = 12, we can construct the following tree:
Provide a ! estimate of the height as a function of n.
Hint: Since ! is just an estimate, we can ignore the elements at the lowest level. We seek an integer h such that
1 + 2 + 3 + 4 + . . . + (h + 1) = n
See Example A2.1 in Appendix 2.
Note: This exercise is contrived but, in fact, the ! estimate of the average height of a binary tree is the same as the answer to this exercise (see Flajolet, [1981]). Get the solution of 9.15
