home / study / engineering / computer science / computer science questions and a

Question

home / study / engineering / computer science / computer science questions and answers / write a method: public iterator shortestpath(t targetone, t targettwo) throws elementnotfoundexception{...

Your question has been posted.

We'll notify you when a Chegg Expert has answered. Post another question.

Next time just snap a photo of your problem. No typing, no scanning, no explanation required.

GET CHEGG STUDY APP

Question: Write a method: public Iterator shortestPath(T targetOne, T targetTwo) throws ElementNotFoundExce...

Edit question

Write a method: public Iterator shortestPath(T targetOne, T targetTwo) throws ElementNotFoundException{

which 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.  

Other methods you may use:

pathToRoot

public Iterator<T> pathToRoot(T targetElement) throws ElementNotFoundException{

ArrayUnorderedList<T> rootList = new ArrayUnorderedList<T>();

pathToRootAgain(targetElement, root, rootList);

if (rootList.isEmpty()==true){

throw new ElementNotFoundException("Binary Tree");

}

return rootList.iterator();

}

Lowest Common Ancestor

public T lowestCommonAncestor( T targetOne, T targetTwo) throws ElementNotFoundException{

Iterator<T> iterator1 = pathToRoot(targetOne);

Iterator<T> iterator2 = pathToRoot(targetTwo);

ArrayUnorderedList<T> lowestPath = new ArrayUnorderedList<T>();

while(iterator1.hasNext()){

lowestPath.addToRear(iterator1.next());

}

while(iterator2.hasNext()){

T temporaryholder = iterator2.next();

//if 'lowest Path' contains the temporary element, return that element

if(lowestPath.contains(temporaryholder)){

return temporaryholder;

}

}

//return the element at the root of the tree

return root.element;

}

Explanation / Answer

//The given program will depict the shortest path between two nodes. coded in c++
#include <bits/stdc++.h>
using namespace std;

struct Node {
struct Node* left, *right;
int val;
};

struct Node* newNode(int val)
{
struct Node* ptr = new Node;
ptr->val = val;
ptr->left = ptr->right = NULL;
return ptr;
}

struct Node* insert(struct Node* root, int val)
{
if (root==null)
root = newNode(val);
else if (root->val > val)
root->left = insert(root->left, val);
else if (root->val < val)
root->right = insert(root->right, val);
return root;
}

//The below functon returns the distance from root assuming root is not null
int distanceFromRoot(struct Node* root, int x)
{
if (root->val == x)
return 0;
else if (root->val > x)
return 1 + distanceFromRoot(root->left, x);
return 1 + distanceFromRoot(root->right, x);
}

//this function will calculate the minimum distance between a and b assuming both are not null
int distanceBetween2(struct Node* root, int a, int b)
{
if (!root)
return 0;

// Both vals lie in left
if (root->val > a && root->val > b)
return distanceBetween2(root->left, a, b);

// Both vals lie in right
if (root->val < a && root->val < b) // same path
return distanceBetween2(root->right, a, b);

// Lie in opposite directions (Root is
// LCA of two nodes)
if (root->val >= a && root->val <= b)
return distanceFromRoot(root, a) +
distanceFromRoot(root, b);
}

//make sure a<b and call to findDistMethod
int findDistMethod(Node *root, int a, int b)
{
if (a > b)
swap(a, b);
return distanceBetween2(root, a, b);
}

int main()
{
struct Node* root = NULL;
root = insert(root, 21);
insert(root, 16);
insert(root, 4);
insert(root, 13);

int a = 4, b = 32;
cout << findDistMethod(root, a,b);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.