Homework Assignment VII Solution



1(10 points) For each part, show the binary search tree that would be created if
keys are in serted in the given order.

a. S U P E R C A T

 b. P E A C R U S T

c. P U R E C A S T



 d. A C E P R S T U


 2(8 points) For each part, start from the original tree1 and draw the resulting binary search tree after the node with the given key is deleted.
Original Tree
a. delete E
b. delete B - move predecessor
 		b. delete B - move successor
c. delete F - move predecessor
 		c. delete F - move successor


3(7 points)

Using tree1 (above) and tree2, shown here, show separately, the result of the calls: 
P(tree1, 0);

and 

P(tree2, 0);
given the function: 
void P(Node* t, int L){
	if (t){
		P(t->right, L+1);
		for (int i = 1; i <= L; i++)
			cout << "   ";
		cout << t->data << endl;
		P(t->left, L+1);
	};
};
This is how we used to draw trees. (before Macs)
P(tree1, 0);

      I
   H
      G
F
         E
      D
         C
   B
      A
 
P(tree2, 0);

A
               I
            G
                  H
               F
         E
      D
         C
   B

Last Updated: May 18, 1997, 1997 11:01 am by

Harriet Fell
College of Computer Science, Northeastern University
360 Huntington Avenue #161CN,
Boston, MA 02115
Internet: fell@ccs.neu.edu
Phone: (617) 373-2198 / Fax: (617) 373-5121
The URL for this document is: http://www.ccs.neu.edu/home/fell/COM1101/HW/HW7/hw7Solution.html