use java to write Find the Shortest Path from one given tree node to another giv
ID: 3918369 • Letter: U
Question
use java to write
Find the Shortest Path from one given tree node to another given tree node
For the 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{
we already have to method:
public Iterator pathToRoot(T targetElement) throws ElementNotFoundException{
ArrayUnorderedList pathToRoot = new ArrayUnorderedList();
pathToRootAgain(targetElement, root, pathToRoot);(there is a mistake, how to change?)
if (pathToRoot.isEmpty() == true){
throw new ElementNotFoundException("Binary Tree");
}
return pathToRoot.iterator();
}
public void PathToRootAgain(T targetElement,T root, int n, ArrayUnorderedList pathToRoot)
{
if (root == null) {
return ;
}
if (root.data == n) {(.data has a mistake how to change?)
return ;
}
if (root.left != null) PathToRootAgain(root.left, n, pathToRoot);(.left can not be resloved, how to change?)
if (root.right != null) PathToRootAgain(root.right, n, pathToRoot) ;
pathToRoot.add(root);(how to create method add(T)?)
return ;
}
public T lowestCommonAncestor( T targetOne, T targetTwo) throws ElementNotFoundException{
Iterator>
Iterator two = pathToRoot(targetTwo);
ArrayUnorderedList ArrayUnorderedList();
while(one.hasNext()){
onPathOne.addToRear(one.next());
}
while(two.hasNext()){
T temp = two.next();
if(onPathOne.contains(temp)){
return temp;
}}
return root.element;
}
Explanation / Answer
import java.util.Iterator; public class TreeTraFind { static int d1 = -1; static int d2 = -1; static int dist = 0; public Iterator pathToRoot(T targetElement) throws ElementNotFoundException{ ArrayUnorderedList pathToRoot = new ArrayUnorderedList(); pathToRootAgain(targetElement, root, pathToRoot);(there is a mistake, how to change?) if (pathToRoot.isEmpty() == true){ throw new ElementNotFoundException("Binary Tree"); } return pathToRoot.iterator(); } public void PathToRootAgain(T targetElement,T root, int n, ArrayUnorderedList pathToRoot) { if (root == null) { return ; } if (root.data == n) {(.data has a mistake how to change?) return ; } if (root.left != null) PathToRootAgain(root.left, n, pathToRoot);(.left can not be resloved, how to change?) if (root.right != null) PathToRootAgain(root.right, n, pathToRoot) ; pathToRoot.add(root);(how to create method add(T)?) return ; } public T lowestCommonAncestor( T targetOne, T targetTwo) throws ElementNotFoundException{ Iterator one = pathToRoot(targetOne); Iterator two = pathToRoot(targetTwo); ArrayUnorderedList onPathOne = new ArrayUnorderedList(); while(one.hasNext()){ onPathOne.addToRear(one.next()); } while(two.hasNext()){ T temp = two.next(); if(onPathOne.contains(temp)){ return temp; }} return root.element; } static int findLevel(Node root, int k, int level) { // Base Case if (root == null) return -1; // If key is present at root, or in left subtree or right subtree, // return true; if (root.key == k) return level; int l = findLevel(root.left, k, level + 1); return (l != -1)? l : findLevel(root.right, k, level + 1); } // This function returns pointer to LCA of two given values n1 and n2. // It also sets d1, d2 and dist if one key is not ancestor of other // d1 --> To store distance of n1 from root // d2 --> To store distance of n2 from root // lvl --> Level (or distance from root) of current node // dist --> To store distance between n1 and n2 static T findDistUtil(T root, int n1, int n2, int lvl){ // Base case if (root == null) return null; // If either n1 or n2 matches with root's key, report // the presence by returning root (Note that if a key is // ancestor of other, then the ancestor key becomes LCA if (root.key == n1){ d1 = lvl; return root; } if (root.key == n2) { d2 = lvl; return root; } // Look for n1 and n2 in left and right subtrees T left_lca = findDistUtil(root.left, n1, n2, lvl + 1); T right_lca = findDistUtil(root.right, n1, n2, lvl + 1); // If both of the above calls return Non-NULL, then one key // is present in once subtree and other is present in other, // So this node is the LCA if (left_lca != null && right_lca != null) { dist = (d1 + d2) - 2*lvl; return root; } // Otherwise check if left subtree or right subtree is LCA return (left_lca != null)? left_lca : right_lca; } // The main function that returns distance between n1 and n2 // This function returns -1 if either n1 or n2 is not present in // Binary Tree. static int shortestPath(T root, int n1, int n2){ d1 = -1; d2 = -1; dist = 0; T lca = findDistUtil(root, n1, n2, 1); // If both n1 and n2 were present in Binary Tree, return dist if (d1 != -1 && d2 != -1) return dist; // If n1 is ancestor of n2, consider n1 as root and find level // of n2 in subtree rooted with n1 if (d1 != -1) { dist = findLevel(lca, n2, 0); return dist; } // If n2 is ancestor of n1, consider n2 as root and find level // of n1 in subtree rooted with n2 if (d2 != -1) { dist = findLevel(lca, n1, 0); return dist; } return -1; } public static main(){ T root = new T(1); root.left = new T(2); root.right = new T(3); root.left.left = new T(4); root.left.right = new T(5); root.right.left = new T(6); root.right.right = new T(7); root.right.left.right = new T(8); System.out.println("Dist(4, 5) = "+shortestPath(root, 4, 5)); System.out.println("Dist(4, 6) = "+shortestPath(root, 4, 6)); } }
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.