For thi last problem, you will find two elements, and return an iterator that ca
ID: 3918328 • Letter: F
Question
For thi last problem, you will 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
}
pathToRoot
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<T> Iterator<T> two = pathToRoot(targetTwo); // Create a new unordered list of generic type T ArrayUnorderedList<T> ArrayUnorderedList<T>(); // 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
public T lowestCommonAncestor( T targetOne, T targetTwo) throws ElementNotFoundException{
Iterator<T>>
Iterator<T> two = pathToRoot(targetTwo);
ArrayUnorderedList<T> ArrayUnorderedList<T>();
while(one.hasNext()){
onPathOne.addToRear(one.next());
}
while(two.hasNext()){
T temp = two.next();
if(onPathOne.contains(temp)){
return temp;
}}
return root.element;
}
public Iterator<T> pathToRoot(T targetElement) throws ElementNotFoundException{
ArrayUnorderedList<T> pathToRoot = new ArrayUnorderedList<T>();
pathToRootAgain(targetElement, root, pathToRoot);
if (pathToRoot.isEmpty() == true){
throw new ElementNotFoundException("Binary Tree");
}
return pathToRoot.iterator();
}
public void PathToRootAgain(T targetElement,T root, int n, ArrayUnorderedList <T> pathToRoot)
{
if (root == null) {
return ;
}
if (root.data == n) {
return ;
}
if (root.left != null) PathToRootAgain(root.left, n, pathToRoot);
if (root.right != null) PathToRootAgain(root.right, n, pathToRoot) ;
pathToRoot.add(root);
return ;
}
//for any query please comment.
//please upvote if find it helpful.
//Thank you.