Find the Shortest Path from one given tree node to another given tree node(use j
ID: 3918487 • Letter: F
Question
Find the Shortest Path from one given tree node to another given tree node(use java to write)
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{
I already write two methods, try to use them in the third method. And I need the format public Iterator shortestPath because I have a test java file need this.
And there is something error in my first two methods, please help me correct them, thank you.
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
SOLUTION:
àAccording to the given data the following code illustrates and it is as follows;
CODE:
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>
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;
}
static int findLevel(Node root, int k, int level)
{
if (root == null)
return -1;
if (root.key == k)
return level;
int l = findLevel(root.left, k, level + 1);
return (l != -1)? l : findLevel(root.right, k, level + 1);
}
static T findDistUtil(T root, int n1, int n2, int lvl){
if (root == null)
return null;
if (root.key == n1){
d1 = lvl;
return root;
}
if (root.key == n2)
{
d2 = lvl;
return root;
}
T left_lca = findDistUtil(root.left, n1, n2, lvl + 1);
T right_lca = findDistUtil(root.right, n1, n2, lvl + 1);
if (left_lca != null && right_lca != null)
{
dist = (d1 + d2) - 2*lvl;
return root;
}
return (left_lca != null)? left_lca : right_lca;
}
static int shortestPath(T root, int n1, int n2){
d1 = -1;
d2 = -1;
dist = 0;
T lca = findDistUtil(root, n1, n2, 1);
if (d1 != -1 && d2 != -1)
return dist;
if (d1 != -1)
{
dist = findLevel(lca, n2, 0);
return dist;
}
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));
}
}
Therefore above is the code to get the required data
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.