1. A binary tree is strictly binary if every nonleaf node has exactly two children. Prove by mathematical induction on the number of leaves that a strictly binary tree with n leaves has exactly 2 n –...

1. A binary tree is strictly binary if every nonleaf node has exactly two children. Prove by mathematical induction on the number of leaves that a strictly binary tree with n leaves has exactly 2 n – 1 nodes.

2. Consider two algorithms for traversing a binary tree. Both are nonrecursive algorithms that use an extra container C for bookkeeping. Both algorithms have the following basic form:

The difference between the two algorithms is the approach for choosing a node N to remove from the container C :

• Algorithm 1: Remove the newest (most recently added) node from C .

• Algorithm 2: Remove the oldest (earliest added) node from C .

a. In what order would each algorithm visit the nodes of the tree in Figure 15-13 ?

b. For each algorithm, describe an appropriate ADT for the bookkeeping container C . What data should the ADT have? Be conservative with the amount of memory needed for the ADT. Also, note that the traversal of a tree should not alter the tree in any way.