526
Graphs and Trees
40. What is the minimum number of nodes and arcs that need to be deleted to reduce a full binary tree of
height ≥ 2 to a forest of 4 binary trees?
41. Let G be a simple graph. Prove that G is a nonrooted tree if and only if G is connected and if the removal
of any single arc from G makes G unconnected.
42. Let G be a simple graph. Prove that G is a nonrooted tree if and only if G is connected and the addition of
one arc to G results in a graph with exactly one cycle.
43. Prove that a binary tree has at most 2
d
nodes at depth d.
44. Prove that a tree with n nodes, n ≥ 2, has at least two nodes of degree 1.
45. a. Draw a full binary tree of height 2. How many nodes does it have?
b. Draw a full binary tree of height 3. How many nodes does it have?
c. Conjecture how many nodes there are in a full binary tree of height h.
46. Prove your conjecture from Exercise 45(c) three different ways.
a. Use induction on the height h of the full binary tree. (Hint: Use Exercise 43.)
b. Add up the nodes at each level of the tree (Hint: Use Exercise 43).
c. Use structural induction.
47. a. Prove that a full binary tree with x internal nodes has 2x + 1 total nodes.
b. Prove that a full binary tree with x internal nodes has x + 1 leaves.
c. Prove that a full binary tree with n nodes has (n − 1)∙2 internal nodes and (n + 1)∙2 leaves.
48. Prove that the number of leaves in any binary tree is 1 more than the number of nodes with two children.
49. Find an expression for the height of a complete binary tree with n nodes. (Hint: Use Exercise 45.)
50. Prove that in the pointer representation of a binary tree with n nodes there are n + 1 null pointers.
(Hint: Use Exercise 48).
51. Find the chromatic number of a tree (see Section 6.1, Exercise 80).
52. Let E be the external path length of a tree, that is, the sum of the path lengths to all the leaves. Let I be the
internal path length, that is, the sum of the path lengths to all the internal nodes. Let i be the number of
internal nodes. Prove that in a binary tree where all internal nodes have two children, E = I + 2i.
53. Let B(n) represent the number of different binary trees with n nodes.
a. Define B(0) to have the value 1 (there is one binary tree with 0 nodes). Prove that B(n) is given by the
recurrence relation
B(1) = 1
B(n) = ∙
n−1
k=0
B(k)B(n − 1 − k)
b. Compare the sequence B(n) to the sequence of Catalan numbers (Exercise 97, Section 4.4). Write the
closed-form expression for B(n).
c. Compute the number of different binary trees with 3 nodes. Draw all these trees.
d. Compute the number of different binary trees with 6 nodes.
54. In the data structure known as a B-tree of order 5, each node of the tree can contain multiple data values,
maintained in sorted order. Between and around the data values at an internal node are arcs that lead to
children of the node. New data values are inserted into the leaf nodes of the tree, but when a leaf (or internal node) gets up to five values, it splits in two and the median value pops up to the next level of the
tree. The figure shows the tree at various points as the data values 1 through 8 are inserted into an initially
empty tree.
Graphs and Trees
40. What is the minimum number of nodes and arcs that need to be deleted to reduce a full binary tree of
height ≥ 2 to a forest of 4 binary trees?
41. Let G be a simple graph. Prove that G is a nonrooted tree if and only if G is connected and if the removal
of any single arc from G makes G unconnected.
42. Let G be a simple graph. Prove that G is a nonrooted tree if and only if G is connected and the addition of
one arc to G results in a graph with exactly one cycle.
43. Prove that a binary tree has at most 2
d
nodes at depth d.
44. Prove that a tree with n nodes, n ≥ 2, has at least two nodes of degree 1.
45. a. Draw a full binary tree of height 2. How many nodes does it have?
b. Draw a full binary tree of height 3. How many nodes does it have?
c. Conjecture how many nodes there are in a full binary tree of height h.
46. Prove your conjecture from Exercise 45(c) three different ways.
a. Use induction on the height h of the full binary tree. (Hint: Use Exercise 43.)
b. Add up the nodes at each level of the tree (Hint: Use Exercise 43).
c. Use structural induction.
47. a. Prove that a full binary tree with x internal nodes has 2x + 1 total nodes.
b. Prove that a full binary tree with x internal nodes has x + 1 leaves.
c. Prove that a full binary tree with n nodes has (n − 1)∙2 internal nodes and (n + 1)∙2 leaves.
48. Prove that the number of leaves in any binary tree is 1 more than the number of nodes with two children.
49. Find an expression for the height of a complete binary tree with n nodes. (Hint: Use Exercise 45.)
50. Prove that in the pointer representation of a binary tree with n nodes there are n + 1 null pointers.
(Hint: Use Exercise 48).
51. Find the chromatic number of a tree (see Section 6.1, Exercise 80).
52. Let E be the external path length of a tree, that is, the sum of the path lengths to all the leaves. Let I be the
internal path length, that is, the sum of the path lengths to all the internal nodes. Let i be the number of
internal nodes. Prove that in a binary tree where all internal nodes have two children, E = I + 2i.
53. Let B(n) represent the number of different binary trees with n nodes.
a. Define B(0) to have the value 1 (there is one binary tree with 0 nodes). Prove that B(n) is given by the
recurrence relation
B(1) = 1
B(n) = ∙
n−1
k=0
B(k)B(n − 1 − k)
b. Compare the sequence B(n) to the sequence of Catalan numbers (Exercise 97, Section 4.4). Write the
closed-form expression for B(n).
c. Compute the number of different binary trees with 3 nodes. Draw all these trees.
d. Compute the number of different binary trees with 6 nodes.
54. In the data structure known as a B-tree of order 5, each node of the tree can contain multiple data values,
maintained in sorted order. Between and around the data values at an internal node are arcs that lead to
children of the node. New data values are inserted into the leaf nodes of the tree, but when a leaf (or internal node) gets up to five values, it splits in two and the median value pops up to the next level of the
tree. The figure shows the tree at various points as the data values 1 through 8 are inserted into an initially
empty tree.