Write the method shortestPath: For this problem,find two elements, and return an
ID: 3918338 • Letter: W
Question
Write the method shortestPath:
For this problem,find two elements, and return an iterator that can traverse the elements along the shortest possible path (following the connections that exist in the tree between parent and child nodes) to get from one given tree node to another given tree node. You can use both the path to root and lowest common ancestor in your solution. This method will be added to the LinkedBinaryTree.java file, and has the following header: public Iterator shortestPath(T targetOne, T targetTwo) throws ElementNotFoundException{
LowestCommonAnscestor.java
}
public T lowestCommonAncestor( T targetOne, T targetTwo) throws ElementNotFoundException{ // Create two iterators that refer to the // Path to root for two elements in a tree // These may throw the ElementNotFoundException Iterator Iterator two = pathToRoot(targetTwo); // Create a new unordered list of generic type T ArrayUnorderedList ArrayUnorderedList(); // While iterator one has more elements while(one.hasNext()){ // Add the next element from iterator one to the // Rear of the unordered list onPathOne.addToRear(one.next()); } // While the second iterator has more elements while(two.hasNext()){ // Create a generic element temp that // Refers to the next element from iterator two T temp = two.next(); // If the unordered list contains temp if(onPathOne.contains(temp)){ // Return the temp element return temp; } } // In the worst case scenario // Return the element at the root of the tree return root.element; }}
Explanation / Answer
import java.util.Iterator;
public class LinkedBinaryTree<T> implements BinaryTreeADT<T> {
protected int count;
protected BinaryTreeNode<T> root;
/**
* Creates an empty binary tree.
*/
public LinkedBinaryTree() {
count = 0;
root = null;
}
/**
* Creates a binary tree with the specified element as its root.
*
* @param element
* the element that will become the root of the new binary tree
*/
public LinkedBinaryTree(T element) {
count = 1;
root = new BinaryTreeNode<T>(element);
}
public LinkedBinaryTree(T element, LinkedBinaryTree<T> leftSubtree, LinkedBinaryTree<T> rightSubtree) {
root = new BinaryTreeNode<T>(element);
count = 1;
if (leftSubtree != null) {
count = count + leftSubtree.size();
root.left = leftSubtree.root;
} else
root.left = null;
if (rightSubtree != null) {
count = count + rightSubtree.size();
root.right = rightSubtree.root;
} else
root.right = null;
}
/**
* Returns a reference to the element at the root
*
* @return a reference to the specified target
* @throws EmptyCollectionException
* if the tree is empty
*/
public T getRoot() throws EmptyCollectionException {
return root.getElement();
}
/**
* Returns true if this binary tree is empty and false otherwise.
*
* @return true if this binary tree is empty
*/
public boolean isEmpty() {
return count == 0;
}
/**
* Returns the integer size of this tree.
*
* @return the integer size of this tree
*/
public int size() {
return count;
}
public boolean contains(T targetElement) {
try {
T junk = this.find(targetElement);
} catch (ElementNotFoundException e) {
return false;
}
return true;
}
public T find(T targetElement) throws ElementNotFoundException {
BinaryTreeNode<T> current = findAgain(targetElement, root);
if (current == null)
throw new ElementNotFoundException("binary tree");
return (current.element);
}
private BinaryTreeNode<T> findAgain(T targetElement, BinaryTreeNode<T> next) {
if (next == null)
return null;
if (next.element.equals(targetElement))
return next;
BinaryTreeNode<T> temp = findAgain(targetElement, next.left);
if (temp == null)
temp = findAgain(targetElement, next.right);
return temp;
}
/**
* Returns a string representation of this binary tree.
*
* @return a string representation of this binary tree
*/
public String toString() {
Iterator<T> temp = iteratorInOrder();
StringBuilder toReturn = new StringBuilder();
while (temp.hasNext())
toReturn.append(temp.next());
return toReturn.toString();
}
public Iterator<T> iteratorInOrder() {
ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
inorder(root, tempList);
return 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<T> node, ArrayUnorderedList<T> tempList) {
if (node != null) {
inorder(node.left, tempList);
tempList.addToRear(node.element);
inorder(node.right, tempList);
}
}
/**
* Performs an preorder traversal on this binary tree by calling an overloaded,
* recursive preorder method that starts with the root.
*
* @return an pre order iterator over this tree
*/
public Iterator<T> iteratorPreOrder() {
ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
preorder(root, tempList);
return tempList.iterator();
}
/**
* 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<T> node, ArrayUnorderedList<T> tempList) {
if (node != null) {
tempList.addToRear(node.getElement());
preorder(node.left, tempList);
preorder(node.right, tempList);
}
}
/**
* 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
*/
public Iterator<T> iteratorPostOrder() {
ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
postorder(root, tempList);
return tempList.iterator();
}
protected void postorder(BinaryTreeNode<T> node, ArrayUnorderedList<T> tempList) {
if (node != null) {
postorder(node.left, tempList);
postorder(node.right, tempList);
tempList.addToRear(node.getElement());
}
}
/**
* Performs a levelorder traversal on this binary tree, using a templist.
*
* @return a levelorder iterator over this binary tree
*/
public Iterator<T> iteratorLevelOrder() {
ArrayUnorderedList<BinaryTreeNode<T>> nodes = new ArrayUnorderedList<BinaryTreeNode<T>>();
ArrayUnorderedList<T> result = new ArrayUnorderedList<T>();
BinaryTreeNode<T> current;
nodes.addToRear(root);
while (!nodes.isEmpty()) {
current = (BinaryTreeNode<T>) nodes.removeFirst();
if (current != null) {
result.addToRear(current.getElement());
nodes.addToRear(current.left);
nodes.addToRear(current.right);
} else {
result.addToRear(null);
}
}
return result.iterator();
}
public Iterator<T> pathToRoot(T targetElement) throws ElementNotFoundException {
//create array list to store the path to the root
ArrayUnorderedList<T> pathToRoot = new ArrayUnorderedList<T>();
//use pathToRootAgain method to fill up pathToRoot
pathToRootAgain(targetElement, root, pathToRoot);
//catch exception if element is not found
if (pathToRoot.isEmpty() == true) {
throw new ElementNotFoundException("Binary Tree");
}
//return iterator filled with elements
return pathToRoot.iterator();
}
protected void pathToRootAgain(T targetElement, BinaryTreeNode<T> node, ArrayUnorderedList<T> pathToRoot) {
//check that current node is not empty
if (node != null) {
//check to see if node is equal to targetElement
if (node.element.equals(targetElement)) {
//add to pathToRoot if it equals
pathToRoot.addToRear(node.element);
} else {
//check left child
pathToRootAgain(targetElement, node.left, pathToRoot);
// if it is empty, then check right child
if (pathToRoot.isEmpty()) {
pathToRootAgain(targetElement, node.right, pathToRoot);
}
// if pathToRoot is not empty, add to rear
if (!pathToRoot.isEmpty()) {
pathToRoot.addToRear(node.element);
}
}
}
}
/**
* Finds the lowestCommonAncestor of node which is between two ancestors
* @param targetOne
* @param targetTwo
* @return
* @throws ElementNotFoundException
*/
public T lowestCommonAncestor(T targetOne, T targetTwo) throws ElementNotFoundException {
//iterate through both targets
Iterator<T>> Iterator<T> two = pathToRoot(targetTwo);
//create list of elements on the first path
ArrayUnorderedList<T> ArrayUnorderedList<T>();
//storing the elements and adding to the rear
while (one.hasNext()) {
onPathOne.addToRear(one.next());
}
//searches through the second list and stores it in temp
while (two.hasNext()) {
T temp = two.next();
//if element is on both paths, return temp
if (onPathOne.contains(temp)) {
return temp;
}
}
//return the lowest common ancestor using above procedures
return root.element;
}
/**
* This method finds the shortest path possible between the two elements which are being targetted
* @param targetOne
* @param targetTwo
* @return iterator of results conveying shortest path
* @throws ElementNotFoundException
*/
public Iterator<T> shortestPath(T targetOne, T targetTwo) throws ElementNotFoundException {
//create the list, result, to store
ArrayUnorderedList<T> result = new ArrayUnorderedList<T>();
//find the lowest common ancestor between two targets
T ancestor = lowestCommonAncestor(targetOne, targetTwo);
Iterator<T> iteratFirst = pathToRoot(targetOne);
//variable used to check element in iteratFirst
T checkFirst = null;
//used to add to result list all elements until ancestor to rear
while(iteratFirst.hasNext() && !ancestor.equals(checkFirst)) {
checkFirst = iteratFirst.next();
result.addToRear(checkFirst);
}
Iterator<T> iteratSecond = pathToRoot(targetTwo);
//create temporary stack for iteratSecond in reverse
ArrayStack<T> tempStack = new ArrayStack<T>();
//variable used to check element in iteratSecond
T checkSecond = null;
//used to add to tempStack the elements in iteratSecond
while(iteratSecond.hasNext() && !ancestor.equals(checkSecond)) {
checkSecond = iteratSecond.next();
if (!checkSecond.equals(ancestor)) {
tempStack.push(checkSecond);
}
}
//add the tempStack values to result
while(!tempStack.isEmpty()) {
result.addToRear(tempStack.pop());
}
//return iterator as result
return result.iterator();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.