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;

}

Answer 1

SOLUTION:

According to the given data the following code illustrates;

The below is the code with the nodes having the shortest paths and it is as follows;

CODE:

#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;
}

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);
}

int distanceBetween2(struct Node* root, int a, int b)
{
if (!root)
return 0;

if (root->val > a && root->val > b)
return distanceBetween2(root->left, a, b);


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

if (root->val >= a && root->val <= b)
return distanceFromRoot(root, a) +
distanceFromRoot(root, b);
}


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;
}

therefore by using the above code that is with respect to the C++ we can get our required output