Using the definition of full binary tree from Question 1, assemble a proof by induction that for all full binary trees, T,

nodes( T ) 2 height( T ) + 1 .

where nodes( T ) and height( T ) are the number of nodes in T and the height of T, respectively. Here we define the height of a tree with a single node to be 0.

A1: Induction Hypothesis P(h): for every full binary tree T with height h, nodes( T ) 2 height( T ) + 1 .

A2: Induction Hypothesis P(n): for every full binary tree T with n internal nodes, nodes( T ) 2 height( T ) + 1 .

A3: Induction Hypothesis P(n): for every full binary tree T with n nodes, nodes( T ) 2 height( T ) + 1 .

B1: Base case P(0): A full binary tree with height 0 has exactly 1 node. Since 1 2 0 + 1, the induction hypothesis holds for P(0).

B2: Base case P(1): A full binary tree with height 1 has exactly 3 nodes. Since 3 2 1 + 1, the induction hypothesis holds for P(1).

B3: Base case P(1): A full binary tree with a single node has height 0. Since 1 2 0 + 1, the induction hypothesis holds for P(0).

C1: Suppose that we have a full binary tree T with height h.

C2: Suppose that we have a full binary tree T with height h+1.

C3: Suppose that we have a full binary tree with n nodes.

C4: Suppose that we have a full binary tree with n+1 nodes.

D1: We construct a new full binary tree T ' by taking two copies of T and adding a new root node x. The first copy of Tbecomes the left subtree of x. The second copy of T becomes the right subtree of x. The T ' constructed this way is also a full binary tree.

D2: Consider the root of T. If we remove the root from T, we have two subtrees T_L and T_R. Both T_L and T_R. are also full binary trees.

D3: Let T be full binary tree with n nodes, where n 1. The tree T must have at least one leaf node x. We construct a new tree T ' by adding two children to x. The T ' constructed this way is also a full binary tree.

D4: Let T be a full binary tree with n+2 nodes. The tree T must have at least one leaf node x. Since T is a full binary tree, the parent of x must have another child y. We construct a new tree T ' by removing x and y from T. The new tree T ' must still be a full binary tree.

E1: By construction, T' must have height h.

E2: By construction, T' must have height h - 1.

E3: By construction, T' must have height h + 1.

E4: By construction, T' must have height at least h.

E5: By construction, T' must have height at least h - 1.

E6: By construction, T' must have height at least h + 1.

E7: By construction one of T_L or T_R must have height h and the other one has at least one node. Let T ' be the subtree that has height h.

E8: By construction one of T_L or T_R must have height h 1 and the other tree has at least one node. Let T ' be the subtree that has height h 1.

E9: By construction one of T_L or T_R must have height h + 1 and the other tree has at least one node. Let T ' be the subtree that has height h + 1.

E10: By construction both T_L and T_R must have height h.

E11: By construction both T_L and T_R must have height h-1.

E12: By construction both T_L and T_R must have height h+1.

F1: Then, by the induction hypothesis, nodes( T ' ) 2 h + 1.

F2: Then, by the induction hypothesis, nodes( T ' ) 2 (h 1) + 1 = 2 h 1.

F3: Then, by the induction hypothesis, nodes( T ' ) 2 (h + 1) + 1 = 2 h + 3.

F4: Then, by the induction hypothesis, nodes( T_L ) 2 h + 1 and nodes( T_R ) 2 h + 1.

F5: Then, by the induction hypothesis, nodes( T_L ) 2 (h 1) + 1 = 2 h 1 and nodes( T_R ) 2 (h 1) + 1 = 2 h 1.

F6: Then, by the induction hypothesis, nodes( T_L ) 2 (h + 1) + 1 = 2 h + 3 and nodes( T_R ) 2 (h + 1) + 1 = 2 h + 3.

G1: Finally, since nodes( T ) = nodes( T ' ) + 1,

G2: Finally, since nodes( T ) nodes( T ' ) + 1,

G3: Finally, since nodes( T ) = nodes( T ' ) - 1,

G4: Finally, since nodes( T ) nodes( T ' ) - 1,

G5: Finally, since nodes( T ) = nodes( T ' ) + 2,

G6: Finally, since nodes( T ) nodes( T ' ) + 2,

G7: Finally, since nodes( T ) = nodes( T ' ) - 2,

G8: Finally, since nodes( T ) nodes( T ' ) - 2,

G9: Finally, since nodes( T ) = nodes( T_L ) + nodes( T_R ) + 1,

G10: Finally, since nodes( T ) nodes( T_L ) + nodes( T_R ) + 1,

G11: Finally, since nodes( T ) = nodes( T_L ) + nodes( T_R ) + 2,

G12: Finally, since nodes( T ) nodes( T_L ) + nodes( T_R ) + 2,

G13: Finally, since nodes( T ) = nodes( T_L ) + nodes( T_R ),

G14: Finally, since nodes( T ) nodes( T_L ) + nodes( T_R ),

H1: by applying some algebra, we get nodes( T ) 2 height( T ) + 1.

H2: by applying some algebra, we get nodes( T ' ) 2 height( T ' ) + 1.

H3: by applying some algebra, we get nodes( T ) 2 height( T ' ) + 1.

H4: by applying some algebra, we get nodes( T ' ) 2 height( T ) + 1.

I1: Therefore, the induction hypothesis holds for all full binary trees with height h and we have completed the proof by induction.

I2: Therefore, the induction hypothesis holds for all full binary trees with height h+1 and we have completed the proof by induction.

I3: Therefore, the induction hypothesis holds for all full binary trees with height h-1 and we have completed the proof by induction.

I4: Therefore, the induction hypothesis holds for all full binary trees with n internal nodes and we have completed the proof by induction.

I5: Therefore, the induction hypothesis holds for all full binary trees with n+1 internal nodes and we have completed the proof by induction.

I6: Therefore, the induction hypothesis holds for all full binary trees with n nodes and we have completed the proof by induction.

I7: Therefore, the induction hypothesis holds for all full binary trees with n+1 nodes and we have completed the proof by induction.