Implementation for the method: Find Path between The node class:  

public class BSTNode> { private T data; private BSTNode left; private BSTNode right; /**  * Create a BST node with the given data.  *  * @param data the data to be stored in this node.  */  public BSTNode(T data) { this.data = data; } /**  * Get the data in this node.  *  * @return data in this node.  */  public T getData() { return data; } /**  * Set the data in this node.  *  * @param data data to be placed into the node.  */  public void setData(T data) { this.data = data; } /**  * Get the node to the left of this node.  *  * @return node to the left.  */  public BSTNode getLeft() { return left; } /**  * Set the node to the left of this node.  *  * @param left new node to the left.  */  public void setLeft(BSTNode left) { this.left = left; } /**  * Get the node to the right of this node.  *  * @return node to the right.  */  public BSTNode getRight() { return right; } /**  * Set the node to the right of this node.  *  * @param right new node to the right.  */  public void setRight(BSTNode right) { this.right = right; } } 

The interface for the method: /** * Finds a path between two elements in the tree, specifically the path  * from data1 to data2, inclusive of both.  *  * To do this, you must first find the deepest common ancestor and add it  * to the list, then traverse to data1 while adding its ancestors to the  * front of the list then traverse to data2 while adding its ancestors to  * the back of the list. Please note that there is no relationship  * between the data parameters in that they may not belong to the same  * branch. You will most likely have to split off and traverse the tree  * for each piece of data.  *  * You may only use 1 list instance to complete this method. This method  * should only need to traverse to the deepest common ancestor once, and  * from that node to each data in one traversal each. Failure to  * do so will result in a penalty.  *  * Should run in O(n).  *  * @param data1 The data to start the path from  * @param data2 The data to end the path on  * @return the unique path between two elements  * @throws IllegalArgumentException if either data1 or data2 is null  * @throws java.util.NoSuchElementException if data1 or data2 is not in  * the tree  */ List findPathBetween(T data1, T data2); 

I'm supposed to implement the method from the BST class :

public class BST> implements BSTInterface { // DO NOT ADD OR MODIFY INSTANCE VARIABLES. private BSTNode root; private int size; /**  * A no argument constructor that should initialize an empty BST.  * YOU DO NOT NEED TO IMPLEMENT THIS CONSTRUCTOR!  */  public BST() { } /**  * Initializes the BST with the data in the Collection. The data in the BST  * should be added in the same order it is in the Collection.  *  * @param data the data to add to the tree  * @throws IllegalArgumentException if data or any element in data is null  */  public BST(Collection data) { if (data == null) { throw new IllegalArgumentException(""); } for (T item : data) { add(item); } } @Override public void add(T data) { if (data == null) { throw new IllegalArgumentException("The data is null"); } root = addRecursive(data, root); } /**  * Takes in data from the add method and uses  * a Node as a reference to recursively find  * where a node needs to be added  * @param data data to be added to tree  * @param root current node/root from subtree  * @return the root of the node.  */  private BSTNode addRecursive(T data, BSTNode root) { if (root == null) { root = new BSTNode(data); size++; } else if (data.compareTo(root.getData()) < 0) { root.setLeft(addRecursive(data, root.getLeft())); } else if (data.compareTo(root.getData()) > 0) { root.setRight(addRecursive(data, root.getRight())); } return root; } @Override public T remove(T data) { if (data == null) { throw new IllegalArgumentException("The data is null"); } BSTNode b = new BSTNode(null); size--; root = removeRecursive(data, root, b); return b.getData(); } /**  * Takes in data to be removed from  * the remove method and uses a Node as a reference  * to recursively find where a node needs to be added  * @param data to be removed from the tree  * @param current the node/root of the tree  * @param limit node placeholder for one of the cases  * @throws NoSuchElementException if the data is not found  * @return the removed node from the tree  */  private BSTNode removeRecursive(T data, BSTNode current, BSTNode limit) { if (current == null) { throw new NoSuchElementException("The data can not be found"); } else if (data.compareTo(current.getData()) < 0) { current.setLeft(removeRecursive(data, current.getLeft(), limit)); } else if (data.compareTo(current.getData()) > 0) { current.setRight(removeRecursive(data, current.getRight(), limit)); } else { limit.setData(current.getData()); if (current.getRight() != null && current.getLeft() != null) { current.setData(findPredecessor(current.getLeft())); current.setLeft(removeRecursive(current.getData(), current.getLeft(), new BSTNode(null))); } else { if (current.getLeft() != null) { current = current.getLeft(); } else { current = current.getRight(); } } } return current; } /**  * Finds the Predecessor of the node to be removed  * @param current : left node of the node to be removed  * @return Predecessor's data  */  private T findPredecessor(BSTNode current) { if (current.getRight() != null) { return findPredecessor(current.getRight()); } else { return current.getData(); } } @Override public T get(T data) { if (data == null) { throw new IllegalArgumentException("The data is null"); } if (!contains(data)) { throw new NoSuchElementException("The data can not be found"); } else { return getRecursive(data, root); } } /**  * Returns the value associated with the given node  *  * @param data the data to add to the tree  * @param current the node that retrieves the data  * @return the current BST node  */  private T getRecursive(T data, BSTNode current) { if (current == null) { return null; } if (data.compareTo(current.getData()) < 0) { return getRecursive(data, current.getLeft()); } else if (data.compareTo(current.getData()) > 0) { return getRecursive(data, current.getRight()); } else { return current.getData(); } } @Override public boolean contains(T data) { if (data == null) { throw new IllegalArgumentException("The data is null"); } return containsRecursive(data, root); } /**  * Returns a boolean value which states whether the value is in the tree  * @param data from contains method  * @param root current node reference  * @return boolean whether value is in the tree  */  private boolean containsRecursive(T data, BSTNode root) { if (root == null) { return false; } if (data.compareTo(root.getData()) < 0) { return containsRecursive(data, root.getLeft()); } else if (data.compareTo(root.getData()) > 0) { return containsRecursive(data, root.getRight()); } else { return true; } } @Override public int size() { return size; } @Override public List preorder() { return preorderHelper(new ArrayList(), root); } /**  * Orders the tree using preorder  * @param list current list of values in preorder  * @param root current node  * @return List<T> in pre order  */  private List preorderHelper(ArrayList list, BSTNode root) { //add current node to array, pre order left, pre order right if (root == null) { return list; } list.add(root.getData()); list = (ArrayList) preorderHelper(list, root.getLeft()); list = (ArrayList) preorderHelper(list, root.getRight()); return list; } @Override public List postorder() { return postorderHelper(new ArrayList(), root); } /**  * Orders the tree using post order  * @param list current list of values in postorder  * @param root current node  * @return List<T> in postorder  */  private List postorderHelper(ArrayList list, BSTNode root) { //post order left, post order right, add current node to array if (root == null) { return list; } list = (ArrayList) postorderHelper(list, root.getLeft()); list = (ArrayList) postorderHelper(list, root.getRight()); list.add(root.getData()); return list; } @Override public List inorder() { return inorderHelper(new ArrayList(), root); } /**  * Orders the tree using inorder  * @param list current list of values in inorder  * @param root current node  * @return List<T> in inorder  */  private List inorderHelper(ArrayList list, BSTNode root) { //in order left, add current node to array, in order right if (root == null) { return list; } inorderHelper(list, root.getLeft()); list.add(root.getData()); inorderHelper(list, root.getRight()); return list; } @Override public List findPathBetween(T data1, T data2) { if (data1 == null || data2 == null) { throw new IllegalArgumentException( "The nodes are invalid and can't be found"); } return null; // THIS METHOD } @Override public void clear() { root = null; size = 0; } @Override public int height() { return heightHelper(root) - 1; } /**  * Gets the height of each subtree to get cumulative height  * @param root current node  * @return int which represents the height + 1  */  private int heightHelper(BSTNode root) { if (root == null) { return 0; } int leftHeight = heightHelper(root.getLeft()); int rightHeight = heightHelper(root.getRight()); int maxHeight = java.lang.Math.max(leftHeight, rightHeight) + 1; return maxHeight; } @Override public BSTNode getRoot() { // DO NOT EDIT THIS METHOD! return root; } } 

I want to implement findpathbetween with my code

FindPathBetween

You will implement a method to calculate the path between two elements in the tree. You will treat the

rst parameter as your starting point and the second as your ending point. Note that either piece of

data could be anywhere in the tree, meaning you will have to at some point make a separate traversal

for each piece of data. You may import Java's LinkedList/ArrayList classes as appropriate for these

methods (but they may only be used for this method and the traversal methods). However, you are

only allowed to use 1 instance of a List (determining which type of List to use is an exercise to you and

is subject to eciency deductions) to store the path. You must only traverse to each element once and

any common ancestors may only be traversed once in total. This path must only include the deepest

common ancestor only. Including other ancestors will result in 0 points. If the rst data parameter is

equivalent to the second data parameter, then the path between the data is simply the data in the tree

itself (note that the length of the list should be 1 in this case).

Generics

If available, use the generic type of the class; do not use the raw type of the class. For example, use new

ArrayList() instead of new ArrayList(). Using the raw type of the class will result in a

penalty.

Forbidden Statements

You may not use these in your code at any time.

break may only be used in switch-case statements

continue

package

System.arraycopy()

clone()

assert()

Arrays class

Array class

Collections class

Collection.toArray()

Reection APIs

Inner or nested classes

The code should be able to work with BST code provided and any additional methods should be private helper methods within the code.