Need help with these two questions. I got getRootElement, getRootNode, getLeft, getRight, size. Just need help for the rest. Base code provided for both classes. I really just need an example on how to implement the given methods. Thanks!

Complete the implementation of LinkedBinaryTree. Specically, implement these methods: get- RootElement(), getRootNode(), getLeft(), getRight(), size(), getHeight(), height(), contains(), toString(), and iteratorPreOrder(). Review the comments in LinkedBinaryTree and BinaryTreeADT for implementation requirements.

[LC PP 11.2 modied] The LinkedBinarySearchTree class is currently using the nd and contains methods of the LinkedBinaryTree class via inheritance. This is not optimal! Implement these two methods for the LinkedBinarySearchTree class, find() and contains(), so that they will be more ecient by making use of the ordering property of a binary search tree. Notice that five other methods in LinkedBinarySearchTree are not yet implemented: removeMax(), findMin(), findMax(), getLeft(), getRight(), findndNode(). If any are needed by your algorithms, implement them, otherwise you may omit them.

Base Code

import java.util.*;

/** * LinkedBinaryTree implements the BinaryTreeADT interface * * @author Lewis and Chase * @version 4.0 */ public class LinkedBinaryTree implements BinaryTreeADT, Iterable { protected BinaryTreeNode root; protected int modCount; /** * Creates an empty binary tree. */ public LinkedBinaryTree() { root = null; }

/** * Creates a binary tree with the specified element as its root. * * @param element the element that will become the root of the binary tree */ public LinkedBinaryTree(T element) { root = new BinaryTreeNode<>(element); } /** * Creates a binary tree with the specified element as its root and the * given trees as its left child and right child * * @param element the element that will become the root of the binary tree * @param left the left subtree of this tree * @param right the right subtree of this tree */ public LinkedBinaryTree(T element, LinkedBinaryTree left, LinkedBinaryTree right) { root = new BinaryTreeNode<>(element); root.setLeft(left.root); root.setRight(right.root); } /** * Returns a reference to the element at the root * * @return a reference to the specified target * @throws EmptyCollectionException if the tree is empty */ @Override public T getRootElement() throws EmptyCollectionException { // TODO: Implement this. } /** * Returns a reference to the node at the root * * @return a reference to the specified node * @throws EmptyCollectionException if the tree is empty */ protected BinaryTreeNode getRootNode() throws EmptyCollectionException { // TODO: Implement this. } /** * Returns the left subtree of the root of this tree. * * @return a link to the left subtree fo the tree */ public LinkedBinaryTree getLeft() { // TODO: Implement this. } /** * Returns the right subtree of the root of this tree. * * @return a link to the right subtree of the tree */ public LinkedBinaryTree getRight() { // TODO: Implement this. } /** * Returns true if this binary tree is empty and false otherwise. * * @return true if this binary tree is empty, false otherwise */ @Override public boolean isEmpty() { return (root == null); }

/** * Returns the integer size of this tree. * * @return the integer size of the tree */ @Override public int size() { // TODO: Implement this. } /** * Returns the height of this tree. * * @return the height of the tree */ public int getHeight() { // TODO: Implement this. } /** * Returns the height of the specified node. * * @param node the node from which to calculate the height * @return the height of the tree */ private int height(BinaryTreeNode node) { // TODO: Implement this. } /** * Returns true if this tree contains an element that matches the * specified target element and false otherwise. * * @param targetElement the element being sought in this tree * @return true if the element in is this tree, false otherwise */ @Override public boolean contains(T targetElement) { // TODO: Implement this. } /** * Returns a reference to the specified target element if it is * found in this binary tree. Throws a ElementNotFoundException if * the specified target element is not found in the binary tree. * * @param targetElement the element being sought in this tree * @return a reference to the specified target * @throws ElementNotFoundException if the element is not in the tree */ public T find(T targetElement) throws ElementNotFoundException { BinaryTreeNode current = findNode(targetElement, root); if (current == null) throw new ElementNotFoundException("LinkedBinaryTree"); return (current.getElement()); }

/** * Returns a reference to the specified target element if it is * found in this binary tree. * * @param targetElement the element being sought in this tree * @param next the element to begin searching from */ private BinaryTreeNode findNode(T targetElement, BinaryTreeNode next) { if (next == null) return null; if (next.getElement().equals(targetElement)) return next; BinaryTreeNode temp = findNode(targetElement, next.getLeft()); if (temp == null) temp = findNode(targetElement, next.getRight()); return temp; } /** * Returns a string representation of this binary tree showing * the nodes in an inorder fashion. Each element will be * separated by a space. * * @return a string representation of this binary tree */ @Override public String toString() { // TODO: Implement this. }

/** * Returns an iterator over the elements in this tree using the * iteratorInOrder method * * @return an in order iterator over this binary tree */ @Override public Iterator iterator() { return iteratorInOrder(); } /** * Performs an inorder traversal on this binary tree by calling an * overloaded, recursive inorder method that starts with * the root. * * @return an in order iterator over this binary tree */ @Override public Iterator iteratorInOrder() { ArrayUnorderedList tempList = new ArrayUnorderedList<>(); inOrder(root, tempList); return new TreeIterator(tempList.iterator()); }

/** * Performs a recursive inorder traversal. * * @param node the node to be used as the root for this traversal * @param tempList the temporary list for use in this traversal */ protected void inOrder(BinaryTreeNode node, ArrayUnorderedList tempList) { if (node != null) { inOrder(node.getLeft(), tempList); tempList.addToRear(node.getElement()); inOrder(node.getRight(), tempList); } }

/** * Performs an preorder traversal on this binary tree by calling * an overloaded, recursive preorder method that starts with * the root. * * @return a pre order iterator over this tree */ @Override public Iterator iteratorPreOrder() { //TODO: Implement this. }

/** * Performs a recursive preorder traversal. * * @param node the node to be used as the root for this traversal * @param tempList the temporary list for use in this traversal */ protected void preOrder(BinaryTreeNode node, ArrayUnorderedList tempList) { //TODO: Implement this. }

/** * Performs an postorder traversal on this binary tree by calling * an overloaded, recursive postorder method that starts * with the root. * * @return a post order iterator over this tree */ @Override public Iterator iteratorPostOrder() { throw new UnsupportedOperationException("preOrder"); }

/** * Performs a recursive postorder traversal. * * @param node the node to be used as the root for this traversal * @param tempList the temporary list for use in this traversal */ protected void postOrder(BinaryTreeNode node, ArrayUnorderedList tempList) { //Not required. }

/** * Performs a levelorder traversal on this binary tree, using a * templist. * * @return a levelorder iterator over this binary tree */ @Override public Iterator iteratorLevelOrder() { ArrayUnorderedList> nodes = new ArrayUnorderedList<>(); ArrayUnorderedList tempList = new ArrayUnorderedList<>(); BinaryTreeNode current;

nodes.addToRear(root); while (!nodes.isEmpty()) { current = nodes.removeFirst(); if (current != null) { tempList.addToRear(current.getElement()); if (current.getLeft() != null) nodes.addToRear(current.getLeft()); if (current.getRight() != null) nodes.addToRear(current.getRight()); } else tempList.addToRear(null); } return new TreeIterator(tempList.iterator()); } /** * Inner class to represent an iterator over the elements of this tree */ private class TreeIterator implements Iterator { private int expectedModCount; private Iterator iter; /** * Sets up this iterator using the specified iterator. * * @param iter the list iterator created by a tree traversal */ public TreeIterator(Iterator iter) { this.iter = iter; expectedModCount = modCount; } /** * Returns true if this iterator has at least one more element * to deliver in the iteration. * * @return true if this iterator has at least one more element to deliver * in the iteration * @throws ConcurrentModificationException if the collection has changed * while the iterator is in use */ @Override public boolean hasNext() throws ConcurrentModificationException { if (!(modCount == expectedModCount)) throw new ConcurrentModificationException(); return (iter.hasNext()); } /** * Returns the next element in the iteration. If there are no * more elements in this iteration, a NoSuchElementException is * thrown. * * @return the next element in the iteration * @throws NoSuchElementException if the iterator is empty */ @Override public T next() throws NoSuchElementException { if (hasNext()) return (iter.next()); else throw new NoSuchElementException(); } /** * The remove operation is not supported. * * @throws UnsupportedOperationException if the remove operation is called */ @Override public void remove() { throw new UnsupportedOperationException(); } } }

*****************base code************

/** * LinkedBinarySearchTree implements the BinarySearchTreeADT interface * with links. * * @author Lewis and Chase * @version 4.0 */ public class LinkedBinarySearchTree extends LinkedBinaryTree implements BinarySearchTreeADT { /** * Creates an empty binary search tree. */ public LinkedBinarySearchTree() { super(); } /** * Creates a binary search with the specified element as its root. * * @param element the element that will be the root of the new binary * search tree */ public LinkedBinarySearchTree(T element) { super(element); if (!(element instanceof Comparable)) throw new NonComparableElementException("LinkedBinarySearchTree"); } /** * Adds the specified object to the binary search tree in the * appropriate position according to its natural order. Note that * equal elements are added to the right. * * @param element the element to be added to the binary search tree */ @Override public void addElement(T element) { if (!(element instanceof Comparable)) throw new NonComparableElementException("LinkedBinarySearchTree");

Comparable comparableElement = (Comparable)element;

if (isEmpty()) root = new BinaryTreeNode(element); else { if (comparableElement.compareTo(root.getElement()) < 0) { if (root.getLeft() == null) this.getRootNode().setLeft(new BinaryTreeNode(element)); else addElement(element, root.getLeft()); } else { if (root.getRight() == null) this.getRootNode().setRight(new BinaryTreeNode(element)); else addElement(element, root.getRight()); } } modCount++; } /** * Adds the specified object to the binary search tree in the * appropriate position according to its natural order. Note that * equal elements are added to the right. * * @param element the element to be added to the binary search tree */ private void addElement(T element, BinaryTreeNode node) { Comparable comparableElement = (Comparable)element; if (comparableElement.compareTo(node.getElement()) < 0) { if (node.getLeft() == null) node.setLeft(new BinaryTreeNode(element)); else addElement(element, node.getLeft()); } else { if (node.getRight() == null) node.setRight(new BinaryTreeNode(element)); else addElement(element, node.getRight()); } } /** * Removes the first element that matches the specified target * element from the binary search tree and returns a reference to * it. Throws a ElementNotFoundException if the specified target * element is not found in the binary search tree. * * @param targetElement the element being sought in the binary search tree * @throws ElementNotFoundException if the target element is not found */ @Override public T removeElement(T targetElement) throws ElementNotFoundException { T result = null;

if (isEmpty()) throw new ElementNotFoundException("LinkedBinarySearchTree"); else { BinaryTreeNode parent = null; if (((Comparable)targetElement).equals(root.element)) { result = root.element; BinaryTreeNode temp = replacement(root); if (temp == null) root = null; else { root.element = temp.element; root.setRight(temp.right); root.setLeft(temp.left); }

modCount--; } else { parent = root; if (((Comparable)targetElement).compareTo(root.element) < 0) result = removeElement(targetElement, root.getLeft(), parent); else result = removeElement(targetElement, root.getRight(), parent); } } return result; } /** * Removes the first element that matches the specified target * element from the binary search tree and returns a reference to * it. Throws a ElementNotFoundException if the specified target * element is not found in the binary search tree. * * @param targetElement the element being sought in the binary search tree * @param node the node from which to search * @param parent the parent of the node from which to search * @throws ElementNotFoundException if the target element is not found */ private T removeElement(T targetElement, BinaryTreeNode node, BinaryTreeNode parent) throws ElementNotFoundException { T result = null; if (node == null) throw new ElementNotFoundException("LinkedBinarySearchTree"); else { if (((Comparable)targetElement).equals(node.element)) { result = node.element; BinaryTreeNode temp = replacement(node); if (parent.right == node) parent.right = temp; else parent.left = temp;

modCount--; } else { parent = node; if (((Comparable)targetElement).compareTo(node.element) < 0) result = removeElement(targetElement, node.getLeft(), parent); else result = removeElement(targetElement, node.getRight(), parent); } } return result; } /** * Returns a reference to a node that will replace the one * specified for removal. In the case where the removed node has * two children, the inorder successor is used as its replacement. * * @param node the node to be removed * @return a reference to the replacing node */ private BinaryTreeNode replacement(BinaryTreeNode node) { BinaryTreeNode result = null; if ((node.left == null) && (node.right == null)) result = null; else if ((node.left != null) && (node.right == null)) result = node.left; else if ((node.left == null) && (node.right != null)) result = node.right; else { BinaryTreeNode current = node.right; BinaryTreeNode parent = node; while (current.left != null) { parent = current; current = current.left; } current.left = node.left; if (node.right != current) { parent.left = current.right; current.right = node.right; } result = current; } return result; } /** * Removes elements that match the specified target element from * the binary search tree. Throws a ElementNotFoundException if * the specified target element is not found in this tree. * * @param targetElement the element being sought in the binary search tree * @throws ElementNotFoundException if the target element is not found */ @Override public void removeAllOccurrences(T targetElement) throws ElementNotFoundException { removeElement(targetElement); try { while (contains((T)targetElement)) removeElement(targetElement); } catch (Exception ElementNotFoundException) { } }

/** * Removes the node with the least value from the binary search * tree and returns a reference to its element. Throws an * EmptyCollectionException if this tree is empty. * * @return a reference to the node with the least value * @throws EmptyCollectionException if the tree is empty */ @Override public T removeMin() throws EmptyCollectionException { T result = null;

if (isEmpty()) throw new EmptyCollectionException("LinkedBinarySearchTree"); else { if (root.left == null) { result = root.element; root = root.right; } else { BinaryTreeNode parent = root; BinaryTreeNode current = root.left; while (current.left != null) { parent = current; current = current.left; } result = current.element; parent.left = current.right; }

modCount--; } return result; }

/** * Removes the node with the highest value from the binary * search tree and returns a reference to its element. Throws an * EmptyCollectionException if this tree is empty. * * @return a reference to the node with the highest value * @throws EmptyCollectionException if the tree is empty */ @Override public T removeMax() throws EmptyCollectionException { // TODO: May need to implement. }

/** * Returns the element with the least value in the binary search * tree. It does not remove the node from the binary search tree. * Throws an EmptyCollectionException if this tree is empty. * * @return the element with the least value * @throws EmptyCollectionException if the tree is empty */ @Override public T findMin() throws EmptyCollectionException { // TODO: May need to implement. }

/** * Returns the element with the highest value in the binary * search tree. It does not remove the node from the binary * search tree. Throws an EmptyCollectionException if this * tree is empty. * * @return the element with the highest value * @throws EmptyCollectionException if the tree is empty */ @Override public T findMax() throws EmptyCollectionException { // TODO: May need to implement. }

// TODO: Implement find. // TODO: Implement contains. /** * Returns the left subtree of the root of this tree. * * @return a link to the left subtree fo the tree */ @Override public LinkedBinarySearchTree getLeft() { // TODO: May need to implement. } /** * Returns the right subtree of the root of this tree. * * @return a link to the right subtree of the tree */ @Override public LinkedBinarySearchTree getRight() { // TODO: May need to implement. } /** * Returns a reference to the specified target element if it is * found in this tree. * * @param targetElement the element being sought in the tree * @param next the tree node to begin searching on */ private BinaryTreeNode findNode(T targetElement, BinaryTreeNode next) { // TODO: May need to implement. } }

******************* BinarytreeADT************

import java.util.Iterator;

/** * BinaryTreeADT defines the interface to a binary tree data structure. * * @author Lewis and Chase * @version 4.0 */ public interface BinaryTreeADT { /** * Returns a reference to the root element * * @return a reference to the root */ public T getRootElement();

/** * Returns true if this binary tree is empty and false otherwise. * * @return true if this binary tree is empty, false otherwise */ public boolean isEmpty();

/** * Returns the number of elements in this binary tree. * * @return the number of elements in the tree */ public int size();

/** * Returns true if the binary tree contains an element that matches * the specified element and false otherwise. * * @param targetElement the element being sought in the tree * @return true if the tree contains the target element */ public boolean contains(T targetElement);

/** * Returns a reference to the specified element if it is found in * this binary tree. Throws an exception if the specified element * is not found. * * @param targetElement the element being sought in the tree * @return a reference to the specified element */ public T find(T targetElement);

/** * Returns the string representation of this binary tree. * * @return a string representation of the binary tree */ public String toString();

/** * Returns an iterator over the elements of this tree. * * @return an iterator over the elements of this binary tree */ public Iterator iterator(); /** * Returns an iterator that represents an inorder traversal on this binary tree. * * @return an iterator over the elements of this binary tree */ public Iterator iteratorInOrder(); /** * Returns an iterator that represents a preorder traversal on this binary tree. * * @return an iterator over the elements of this binary tree */ public Iterator iteratorPreOrder();

/** * Returns an iterator that represents a postorder traversal on this binary tree. * * @return an iterator over the elements of this binary tree */ public Iterator iteratorPostOrder();

/** * Returns an iterator that represents a levelorder traversal on the binary tree. * * @return an iterator over the elements of this binary tree */ public Iterator iteratorLevelOrder(); }

***************BinarySearchTree ADT***********8

/** * BinarySearchTreeADT defines the interface to a binary search tree. * * @author Lewis and Chase * @version 4.0 */ public interface BinarySearchTreeADT extends BinaryTreeADT { /** * Adds the specified element to the proper location in this tree. * * @param element the element to be added to this tree */ public void addElement(T element);

/** * Removes and returns the specified element from this tree. * * @param targetElement the element to be removed from the tree * @return the element to be removed from the tree */ public T removeElement(T targetElement); /** * Removes all occurences of the specified element from this tree. * * @param targetElement the element to be removed from the tree */ public void removeAllOccurrences(T targetElement); /** * Removes and returns the smallest element from this tree. * * @return the smallest element from the tree. */ public T removeMin();

/** * Removes and returns the largest element from this tree. * * @return the largest element from the tree */ public T removeMax(); /** * Returns the smallest element in this tree without removing it. * * @return the smallest element in the tree */ public T findMin();

/** * Returns the largest element in this tree without removing it. * * @return the largest element in the tree */ public T findMax(); }