4.3 (Include DList.java in your solution zip archive) Here is the Java implementation of three useful methods (which are not currently in Dlist).

 /** * Removes the head node from this DList. It would be inadvisable to call this method on an * empty list because we do not check for that condition. Returns the data stored in the head * node. */ 

 protected Integer removeHead() { Integer data = getHead().getData(); if (getSize() == 1) { 

 setHead(null); 

 setTail(null); } else { 

 getHead().getNext().setPrev(null); 

 setHead(getHead().getNext()); } 

 setSize(getSize() - 1); 

 return data; } 

 /** * Removes an interior node pNode from this DList. It would be inadvisable to call this method * when pNode is null because we do not check for that condition. Returns the data stored in * pNode. */ 

 protected Integer removeInterior(Node pNode) { Integer data = pNode.getData(); pNode.getPrev().setNext(pNode.getNext()); pNode.getNext().setPrev(pNode.getPrev()); setSize(getSize() - 1); 

 return data; } 

 /** * Removes the tail node from this DList. It would be inadvisable to call this method on an * empty list because we do not check for that condition. Returns the data stored in the tail * node. */ 

 protected Integer removeTail() { Integer data = getTail().getData(); if (getSize() == 1) { 

 setHead(null); 

 setTail(null); } else { 

 getTail().getPrev().setNext(null); 

 setTail(getTail().getPrev()); } 

 setSize(getSize() - 1); 

 return data; } 

Using these three methods, rewrite the provided remove(index) method to make the code in that method simpler and more readable (my new and improved remove() method is half-a-dozen lines of code). Be sure to run the test cases in DListTest to ensure that your new remove() method still works correctly. Also, make sure remove() throws an IndexOutOfBoundsException if pIndex is less than 0 or greater than or equal to getSize().

4.9 (4 bonus pts) Write a method void split(int pIndex, DList pLeft, DList pRight) that will "split" this DList (the one on which the method is invoked) into a left sublist pLeft and a right sublist pRight. The elements of pLeft will consist of list elements at indices 0, 1, 2, ..., pIndex - 1. The elements of pRight will consist of list elements at indices pIndex, pIndex + 1, ..., getSize() - 1. Note that pLeft and pRight must be created (and are assumed to be empty) before calling split(). For example:

 DList list = new DList(); // list = { } 

 list.append(3); list.append(5); list.append(7); list.append(11); 

 list.append(13); list.append(17); list.append(19); list.append(29); 

 // list = { 3, 5, 7, 11, 13, 17, 19, 29 } 

 DList left = new DList, right = new DList(); 

 list.split(5, left, right); 

 // left = { 3, 5, 7, 11, 13 }, right = { 17, 19, 29 } 

*****************************************************************

BinaryTree.java

public class BinaryTree {

// These constants are passsed to traverse() to specify the type of traversal. public static final int INORDER = 0; public static final int LEVEL_ORDER = 1; public static final int POSTORDER = 2; public static final int PREORDER = 3;

/** * A BinaryTree consists of a Node which is the root of the tree. The Node objects contains * references to the left and right child nodes of mRoot. */ private Node mRoot;

/** * Create a new empty BinaryTree storing no data. */ public BinaryTree() { this(null); }

/** * Create a new BinaryTree with the root storing pData. The left and right subtrees are set to * null. */ public BinaryTree(E pData) { this(pData, null, null); }

/** * Create a new BinaryTree with the root storing pData. If pLeft is null, then the root of this * BinaryTree will not have a left subtree. If pLeft is non-null, then pLeft will become the * left subtree of the root of this BinaryTree. To do that, we make the left child reference * of the root of this BinaryTree refer to the root of the subtree pLeft. pRight is handled in * a similar manner. */ public BinaryTree(E pData, BinaryTree pLeft, BinaryTree pRight) { Node leftChild = pLeft == null ? null : pLeft.getRoot(); Node rightChild = pRight == null ? null : pRight.getRoot(); setRoot(new Node(pData, leftChild, rightChild)); }

/** * Removes all of the Nodes in this BinaryTree. After clear() returns, this BinaryTree will be * an empty tree. */ public void clear() { prune(getRoot()); setRoot(null); }

/** * Searches the tree rooted at pRoot for a node containing pData. Returns a reference to the * node or null if pData is not contained within the tree. */ protected Node findNode(Node pRoot, E pData) { if (pRoot == null) return null; if (pRoot.getData().equals(pData)) return pRoot; Node node = findNode(pRoot.getLeft(), pData); if (node != null) return node; return findNode(pRoot.getRight(), pData); }

/** * Returns the height of this BinaryTree. */ public int getHeight() { return getHeight(getRoot()); }

/** * Returns the height of the subtree rooted at pRoot where the height is the maximum of the * heights of the left and right subtrees of pRoot. */ protected int getHeight(Node pRoot) { int heightLeft = 0, heightRight = 0; if (pRoot == null) return 0; if (pRoot.hasLeft()) heightLeft = getHeight(pRoot.getLeft()) + 1; if (pRoot.hasRight()) heightRight = getHeight(pRoot.getRight()) + 1; return Math.max(heightLeft, heightRight); }

/** * Accessor method for mRoot. */ protected Node getRoot() { return mRoot; }

/* * Returns true if this BinaryTree is an empty tree. */ public boolean isEmpty() { return getRoot() == null; }

/** * Returns true if this BinaryTree is full. */ protected boolean isFull() { return isFull(getRoot()); }

/** * Returns true if the subtree rooted at pRoot is a full binary tree. */ protected boolean isFull(Node pRoot) { if (pRoot.isLeaf()) return true; boolean leftFull = pRoot.hasLeft() ? isFull(pRoot.getLeft()) : false; boolean rightFull = pRoot.hasRight() ? isFull(pRoot.getRight()) : false; return leftFull && rightFull; }

/** * Creates a new Iterator over this BinaryTree. The current node of the returned Iterator will * be the root node of this BinaryTree. */ public Iterator iterator() { return new Iterator(this); }

/** * Prunes the tree rooted at pTree by pruning the left and right subtrees and then setting * the left and right references of the root node to null. Note: this method does not delete * the data stored in the root node of pTree, nor does it set the root node of pTree to null. */ protected void prune(Node pRoot) { if (pRoot == null) return; prune(pRoot.getLeft()); pRoot.setLeft(null); prune(pRoot.getRight()); pRoot.setRight(null); }

/** * Prunes only the left subtree of this BinaryTree. */ protected void pruneLeft(Node pRoot) { prune(pRoot.getLeft()); pRoot.setLeft(null); }

/** * Prunes only the right subtree of this BinaryTree. */ protected void pruneRight(Node pRoot) { prune(pRoot.getRight()); pRoot.setRight(null); }

/** * Mutator method for mRoot. */ protected void setRoot(Node pRoot) { mRoot = pRoot; }

/** * Performs a traversal specified by pWhich (which must be one of the constants INORDER, * LEVEL_ORDER, POSTORDER, or PREORDER) on this BinaryTree. pVisitor is an object which * implements the BinaryTreeVisitor interface. As each Node is visited during the traversal, * the visit(E data) method will be called on pVisitor. */ public void traverse(int pWhich, BinaryTreeVisitor pVisitor) { if (pWhich == LEVEL_ORDER) traverseLevelOrder(getRoot(), pVisitor); traverse(pWhich, getRoot(), pVisitor); }

/** * See traverse(int, BinaryTreeVisitor). * * Performs a traversal specified by pWhich (which must be one of the constants INORDER, * LEVEL_ORDER, POSTORDER, or PREORDER) on the subtree rooted at pNode. */ protected void traverse(int pWhich, Node pRoot, BinaryTreeVisitor pVisitor) { if (pRoot == null) return; switch (pWhich) { case INORDER: traverse(pWhich, pRoot.getLeft(), pVisitor); pVisitor.visit(pRoot.getData()); traverse(pWhich, pRoot.getRight(), pVisitor); break; case POSTORDER: traverse(pWhich, pRoot.getLeft(), pVisitor); traverse(pWhich, pRoot.getRight(), pVisitor); pVisitor.visit(pRoot.getData()); break; case PREORDER: pVisitor.visit(pRoot.getData()); traverse(pWhich, pRoot.getLeft(), pVisitor); traverse(pWhich, pRoot.getRight(), pVisitor); break; } }

/** * Make a level order traversal of pTree. */ protected void traverseLevelOrder(Node pRoot, BinaryTreeVisitor pVisitor) { Queue> nodeQueue = new Queue(); nodeQueue.enqueue(pRoot); while (!nodeQueue.isEmpty()) { Node root = nodeQueue.dequeue(); pVisitor.visit(root.getData()); if (root.hasLeft()) nodeQueue.enqueue(root.getLeft()); if (root.hasRight()) nodeQueue.enqueue(root.getRight()); } }

//********************************************************************************************** // STATIC NESTED CLASS: Node //**********************************************************************************************

/** * The data for each element of the BinaryTree is stored in a Node object. A Node object * contains three instance variables: (1) mData is a reference to the data stored in the Node; * (2) mLeft is a reference to the left child Node; and (3) mRight is a reference to the right * child Node. * * Note that Node is declared as protected so it is not visible to other classes but it is * accessible to subclasses of BinaryTree. */ protected static class Node { /** * The data stored in this Node. */ E mData;

/** * A reference to the left child Node of this Node. */ Node mLeft;

/** * A reference to the right child Node of this Node. */ Node mRight;

/** * Creates a new Node storing no data and with mLeft and mRight set to null. */ public Node() { this(null); }

/** * Creates a new Node storing pData as the data and with mLeft and mRight set to null. */ public Node(E pData) { this(pData, null, null); }

/** * Creates a new Node storing pData as the data, mLeft initialized to pLeft, and mRight * initialized to pRight. */ public Node(E pData, Node pLeft, Node pRight) { setData(pData); setLeft(pLeft); setRight(pRight); }

/** * Accessor method for the mData instance variable. */ public E getData() { return mData; }

/** * Accessor method for the mLeft instance variable. */ public Node getLeft() { return mLeft; }

/** * Returns the number of children of this Node. */ public int getNumChildren() { int num = 0; if (hasLeft()) ++num; if (hasRight()) ++ num; return num; }

/** * Accessor method for the mRight instance variable. */ public Node getRight() { return mRight; }

/** * Returns true if this Node has a left child Node. */ public boolean hasLeft() { return getLeft() != null; }

/** * Returns true if this Node has a right child Node. */ public boolean hasRight() { return getRight() != null; }

/** * Returns true if this Node is a leaf node. */ public boolean isLeaf() { return !hasLeft() && !hasRight(); }

/** * Mutator method for the mData instance variable. */ public void setData(E pData) { mData = pData; }

/** * Mutator method for the mLeft instance variable. */ public void setLeft(Node pLeft) { mLeft = pLeft; }

/** * Mutator method for the mRight instance variable. */ public void setRight(Node pRight) { mRight = pRight; }

/** * Returns a string representation of this Node where we define the string representation * to be the string representation of the data stored in this Node. */ @Override public String toString() { return "" + getData(); } }

//********************************************************************************************** // STATIC NESTED CLASS: Iterator //**********************************************************************************************

/** * Implements an iterator that will iterate over the Nodes of the BinaryTree. */ public static class Iterator {

/** * A reference to the current Node of the Iterator. */ Node mCurrent;

/** * This stack stores references to the parent Nodes. As the Iterator moves left and right * downward, parent Nodes are pushed on the stack. When moveUp() is called the parent of * the current Node will be on top of the stack. Note: when moveToRoot() is called the * stack must be emptied. */ Stack> mStack;

/** * A reference to the BinaryTree over which this Iterator iterates. */ BinaryTree mTree;

/** * Create an Iterator to iterate over the BinaryTree pTree. */ public Iterator(BinaryTree pTree) { setTree(pTree); setCurrent(getTree().getRoot()); setStack(new Stack>()); }

/** * Create a new Node containing pData to be the left child of the current Node. */ public void addLeft(E pData) throws EmptyTreeException { if (getTree().isEmpty()) throw new EmptyTreeException(); pruneLeft(); getCurrent().setLeft(new Node(pData)); }

/** * Create a new Node containing pData to be the right child of the current Node. */ public void addRight(E pData) throws EmptyTreeException { if (getTree().isEmpty()) throw new EmptyTreeException(); pruneRight(); getCurrent().setRight(new Node(pData)); }

/** * Searches the binary tree rooted at the current node for pData. If found, the current * Node is changed to the Node containing pData and true is returned. If not found, the * current node will not be changed and false will be returned. */ public boolean find(E pData) { Node node = getTree().findNode(getCurrent(), pData); if (node != null) setCurrent(node); return node != null; }

/** * Returns the data stored in the current Node. */ public E get() { return (E)mCurrent.getData(); }

/** * Protected accessor method for mCurrent. */ protected Node getCurrent() { return mCurrent; }

/** * Protected accessor method for mStack. */ protected Stack> getStack() { return mStack; }

/** * Protected accessor method for mTree. */ protected BinaryTree getTree() { return mTree; }

/** * Returns the height of the subtree rooted at the current Node. */ public int getHeight() { return getTree().getHeight(getCurrent()); }

/** * Returns true if the subtree rooted at the current Node is a full binary tree. */ public boolean isFull() { return getTree().isFull(getCurrent()); }

/** * Moves this Iterator to the left child of the current Node. */ public void moveLeft() { if (getCurrent().hasLeft()) { getStack().push(getCurrent()); setCurrent(getCurrent().getLeft()); } }

/** * Moves this Iterator to the right child of the current Node. */ public void moveRight() { if (getCurrent().hasRight()) { getStack().push(getCurrent()); setCurrent(getCurrent().getRight()); } }

/** * Moves this Iterator to the root Node of the tree. */ public void moveToRoot() { // Note: we have to empty the stack. getStack().clear(); setCurrent(getTree().getRoot()); }

/** * Moves the iterator up to the parent Node of the current Node. */ public void moveUp() { setCurrent(getStack().pop()); }

/** * Prunes both the left and right subtrees of the current Node. */ public void prune() { pruneLeft(); pruneRight(); }

/** * Prunes the left subtree of the current Node. */ public void pruneLeft() { getTree().pruneLeft(getCurrent()); }

/** * Prunes the right subtree of the current Node. */ public void pruneRight() { getTree().pruneRight(getCurrent()); }

/** * Changes the data stored in the current Node. */ public void set(E pData) { getCurrent().setData(pData); }

/** * Protected mutator method for mCurrent. */ protected void setCurrent(Node pCurrent) { mCurrent = pCurrent; }

/** * Protected mutator method for mTree. */ protected void setTree(BinaryTree pTree) { mTree = pTree; }

/** * Protected mutator method for mStack. */ protected void setStack(Stack> pStack) { mStack = pStack; }

/** * Performs a traversal specified by pWhich (which must be one of the constants INORDER, * LEVEL_ORDER, POSTORDER, or PREORDER) on the subtree rooted at the current Node. * pVisitor is an object which implements the BinaryTreeVisitor interface. As each Node * is visited during the traversal, the visit(E data) method will be called on pVisitor. */ public void traverse(int pWhich, BinaryTreeVisitor pVisitor) { getTree().traverse(pWhich, getCurrent(), pVisitor); } } }

**************************************************

Here is the BinaryTreeNode.java code to modify/edit:

public interface BinaryTreeNode { E getData(); void setData(E data); BinaryTreeNode getParent(); BinaryTreeNode getLeft();

void setLeft(BinaryTreeNode child); /** * Returns the right child of this node, or null if it does * not have one. */ BinaryTreeNode getRight(); /** * Removes child from its current parent and inserts it as the * right child of this node. If this node already has a right * child it is removed. * @exception IllegalArgumentException if the child is * an ancestor of this node, since that would make * a cycle in the tree. */ void setRight(BinaryTreeNode child); void removeFromParent(); /** * Visits the nodes in this tree in preorder. */ void traversePreorder(Visitor visitor); void traversePostorder(Visitor visitor); /** * Visits the nodes in this tree in inorder. */ void traverseInorder(Visitor visitor); /** * Simple visitor interface. */ public interface Visitor { void visit(BinaryTreeNode node); } }

5.4 If n is the size of the tree, what is the worst case time complexity of getSize() in big O notation?

5.9 (1 bonus pt) How much faster, expressed as a percentage, are searches in this particular BST than searches in this particular linked list?

Now for element 1, Comparison= 1*5=5

for element 2, Comparison= 1*4=4

for element 3, Comparison= 1*3=3

for element 4, Comparison= 1*2=2

for element 5, Comparison= 1*1=1

for element 6, Comparison= 1*4=4

for element 7, Comparison= 1*3=3

for element 8, Comparison= 1*2=2

for element 9, Comparison= 1*3=3

So total comparison=27, Total nodes in BST=9

Average Comparison= 27/9=3

5.3 (Include your modified BinaryTree.java source code file in your homework solution zip archive) Add a method int getSize to BinaryTree that returns the size of the binary tree where the size of the tree is defined to be the number of nodes. Here is how I want you to implement this method. Write a local class (see Week 3: Objects and Classes 11 : Section 2) in getSize() named Counter which implements the BinaryTree Vistor interface Counter interface implementsBinary Tree VisitorsE visit (pData: E): void mCount: int +Counter( ctor +getCount): int +visit (pData: E): void The Counter constructor initializes mCount to 0. visit) simply increments mCount when it is called. Once the local class is completed, we can count the nodes in the tree by performing a traversal (it does not matter which type of traversal we performe because each node will be visited during the traversal; the order in which we visit them does not matter for this application). To perform the traversal write public int getSizeOf // Implement local class named Counter here Counter counter - new Counter O; traverse (LEVEL ORDER, counter); return counter.getCountO 5.3 (Include your modified BinaryTree.java source code file in your homework solution zip archive) Add a method int getSize to BinaryTree that returns the size of the binary tree where the size of the tree is defined to be the number of nodes. Here is how I want you to implement this method. Write a local class (see Week 3: Objects and Classes 11 : Section 2) in getSize() named Counter which implements the BinaryTree Vistor interface Counter interface implementsBinary Tree VisitorsE visit (pData: E): void mCount: int +Counter( ctor +getCount): int +visit (pData: E): void The Counter constructor initializes mCount to 0. visit) simply increments mCount when it is called. Once the local class is completed, we can count the nodes in the tree by performing a traversal (it does not matter which type of traversal we performe because each node will be visited during the traversal; the order in which we visit them does not matter for this application). To perform the traversal write public int getSizeOf // Implement local class named Counter here Counter counter - new Counter O; traverse (LEVEL ORDER, counter); return counter.getCountO