Q1
A) 
      Differences:
	  1: abstract class can have instance variable  but interface cannot.
	  2: abstract class can have method body  but interface cannot.
	  3: abstract class can have only 1 (parent) superclass, interface can have many parents	 
	  4: abstract class can implement an interface but not the opposite (meaningless!)
	Similarities:
	  1: for both cannot instantiate (create an object )
	  2: both can have constants
  	  3. both can have method headers
	  4: both support inheritance (can be derived from a parent)

B) 


                   5
                /       \
              1          7
                \       /
                 4     6
                /
               2
                \
                 3      


C)   
   	
Inorder: 1 2 3 4 5 6 7
Preorder:5 1 4 2 3  7 6
 
Q2. 
A) public class DLList<E> {
	
	private Node<E> head, tail;

   public void append(DLList<E> lst2) {
     if (head == null) {
        head = lst2.head;
        tail = lst2.tail;
      } if (lst.head == null) {
          return;
      }else {
        tail.next = lst2.head;
        lst2.head.prev = tail;
        tail = lst2.tail;
      }
  }

B) 
1)  {} and {} both lists empty
2) {} and  {1,…n} empty and nonempty
3) {1,…n} and {}  non-empty and empty
4) {1} and {2}  both have 1 element
5) {1} and {2,3,4,5,..} 1 element append with many elements
6) {2,3,4,5,..} and {1}  many  elements append with  1 elements
7) {1,2,3,4} {5,6.,7,8,9} both many elements


C) 
    public class   <E extends Comparable<? Super E>> DLList<E>  {
           NO change is needed.
    }
 
Q3. 
A)
1:  
       O
   
2: impossible

3:
         O
        / \
       O   O
4. impossible                                                                       
5:
         O               O
        / \             / \
       O   O           O   O
      / \                 / \
     O   O               O   O

6: impossible

B)
  public boolean isFullTree(){
         return isFullTreeHelper(root);
    }

    private boolean isFullTreeHelper (BNode r){
         if (r == null){
		     return false;
         } else if (r.left == null   && r.right == null) {
			 return true;
         } else {
	     	 return (isFullTreeHelper(r.left) && isFullTreeHelper(r.right));
         } 
    }


Q4)
1. Jerry: burp
2.	Done feeding
3.	Ok, let's go for a walk
4.	Jerry: I love walking!
5.	My, that was fun!
6.	----------------
7.	Exception: Jerry: I'm a dog. No fish please!
8.	Ok, let's go for a walk
9.	Exception: Jerry: I cannot walk, I'm hungry!
10.	Tom: meow
11.	Exception: Tom: meow, meow, No thanks I am full!
12.	Ok, let's go for a walk
13.	Tom: I love walking!
14.	My, that was fun!