USA: +1 (725) 712-1730 
Sign in
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<T extends Comparable<? super T>> implements BSTInterface<T> {
// DO NOT ADD OR MODIFY INSTANCE VARIABLES.
private BSTNode<T> 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<T> 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<T> addRecursive(T data, BSTNode<T> root) {
if (root == null) {
root = new BSTNode<T>(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<T> b = new BSTNode<T>(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<T> removeRecursive(T data, BSTNode<T> current,
BSTNode<T> 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<T>(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<T> 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<T> 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<T> 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<T> preorder() {
return preorderHelper(new ArrayList<T>(), 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<T> preorderHelper(ArrayList<T> list, BSTNode<T> root) {
//add current node to array, pre order left, pre order right
if (root == null) {
return list;
}
list.add(root.getData());
list = (ArrayList<T>) preorderHelper(list, root.getLeft());
list = (ArrayList<T>) preorderHelper(list, root.getRight());
return list;
}
@Override
public List<T> postorder() {
return postorderHelper(new ArrayList<T>(), 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<T> postorderHelper(ArrayList<T> list, BSTNode<T> root) {
//post order left, post order right, add current node to array
if (root == null) {
return list;
}
list = (ArrayList<T>) postorderHelper(list, root.getLeft());
list = (ArrayList<T>) postorderHelper(list, root.getRight());
list.add(root.getData());
return list;
}
@Override
public List<T> inorder() {
return inorderHelper(new ArrayList<T>(), 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<T> inorderHelper(ArrayList<T> list, BSTNode<T> 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<T> 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<T> 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<T> 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<Integer>() 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.
Expert Answer
BST.java
import java.util.Collection;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.LinkedList;
public class BST<T extends Comparable<? super T>> implements BSTInterface<T> {
private BSTNode<T> root;
private int size;
/**
* A no argument constructor that should initialize an empty BST.
*/
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<T> data) {
for (T item : data) {
if (item == null) {
throw new IllegalArgumentException(“The collection contained”
+ ” null data and couldn’t be added.”);
}
add(item);
}
}
@Override
public void add(T data) {
if (data == null) {
throw new IllegalArgumentException(“Input data is null, please”
+ ” use a non-null input.”);
}
// Most General Case:
root = addNode(data, root);
}
/**
* Recursive helper method to add a new node to the tree using pointer
* reinforcement.
* A successful add indicates that a location was found and there are
* no duplicate nodes in the tree.
*
* @param data the data to be added
* @param node the node that is being searched through currently
* @return whether the data was added successfully or not
*/
private BSTNode<T> addNode(T data, BSTNode<T> node) {
if (node == null) {
size++;
return new BSTNode<>(data);
} else if (data.compareTo(node.getData()) > 0) {
node.setRight(addNode(data, node.getRight()));
} else if (data.compareTo(node.getData()) < 0) {
node.setLeft(addNode(data, node.getLeft()));
}
return node;
}
@Override
public T remove(T data) {
if (data == null) {
throw new java.lang.IllegalArgumentException(“Input data is null,”
+ ” please use a non-null input.”);
}
BSTNode<T> dummy = new BSTNode<T>(null);
root = removeNode(root, dummy, data);
size–;
return dummy.getData();
}
/**
* Recursive helper method to help remove a certain node from the tree
*
* @param node the node being searched through currently
* @param dummy a dummy node to store data
* @param data the data being searched for and removed
* @throws java.util.NoSuchElementException if the node is not found
* @return the removed node
*/
private BSTNode<T> removeNode(BSTNode<T> node, BSTNode<T> dummy, T data) {
if (node == null) {
throw new java.util.NoSuchElementException(“The data to be removed”
+ ” does not exist in this tree. Please use a valid input ”
+ “next time.”);
}
int compare = data.compareTo(node.getData());
if (compare < 0) {
node.setLeft(removeNode(node.getLeft(), dummy, data));
} else if (compare > 0) {
node.setRight(removeNode(node.getRight(), dummy, data));
} else {
dummy.setData(node.getData());
if (isLeaf(node)) {
return null;
} else if (node.getRight() == null) {
return node.getLeft();
} else if (node.getLeft() == null) {
return node.getRight();
} else {
T pred = findPredecessor(node.getLeft()).getData();
node.setLeft(removeNode(node.getLeft(),
new BSTNode<>(null), pred));
node.setData(pred);
}
}
return node;
}
/**
* Helper method help find the predecessor, or right most node
* in a branch of the tree
*
* @param node the node being searched through currently
* @return the node holding the largest data, or the predecessor
*/
private BSTNode<T> findPredecessor(BSTNode<T> node) {
if (node != null) {
while (node.getRight() != null) {
node = node.getRight();
}
}
return node;
}
@Override
public T get(T data) {
if (data == null) {
throw new IllegalArgumentException(“Input data is null, please”
+ ” use a non-null input.”);
} else {
return getNode(data, root);
}
}
/**
* Recursive helper method to find and get a node within the tree.
*
* @param data the data to be returned if found
* @param node the node that is currently being searched through
* @throws NoSuchElementException if the input data is not found
* @return the data from the found node (not the input data)
*/
private T getNode(T data, BSTNode<T> node) {
if (node != null) {
if (data.compareTo(node.getData()) == 0) {
// Return the data if the it was found
return node.getData();
} else if (data.compareTo(node.getData()) < 0) {
// If the data is less than the node, search the left side
return getNode(data, node.getLeft());
} else if (data.compareTo(node.getData()) > 0) {
// If the data is less than the node, search the right side
return getNode(data, node.getRight());
}
}
// Throw an exception if the node is not found
throw new NoSuchElementException(“The input is not contained in this”
+ ” tree. Consider adding that data.”);
}
@Override
public boolean contains(T data) {
if (data == null) {
throw new IllegalArgumentException(“Input data is null, please”
+ ” use a non-null input.”);
} else {
return search(data, root);
}
}
/**
* Search through the tree looking for some particular data within a
* node.
* A successful search indicates that a node containing the same data
* as the one in question was found within the tree
*
* @param data the data being searched for
* @param node the node being searched through
* @return whether the node was found or not
*/
private boolean search(T data, BSTNode<T> node) {
if (node != null) {
if (data.compareTo(node.getData()) == 0) {
// Return true if the data was found
return true;
} else if (data.compareTo(node.getData()) < 0) {
// If the data is less than the node, search its left side
return search(data, node.getLeft());
} else if (data.compareTo(node.getData()) > 0) {
// If the data is less than the node, search its right side
return search(data, node.getRight());
}
}
// Return false if the data is never found
return false;
}
@Override
public int size() {
return size;
}
@Override
public List<T> preorder() {
// node, left, right; base: is leaf
LinkedList<T> traversal = new LinkedList<>();
return preorderTraversal(root, traversal);
}
/**
* Recursive helper method to traverse through the tree, saving each
* particular node to a list.
* Preorder Traversal is defined as marking Node, Node.left, Node.right in
* that order.
*
* @param node the node being traversed through currently
* @param traversal the list that the nodes are recorded in
* @return the list of all visited nodes
*/
private List<T> preorderTraversal(BSTNode<T> node, List<T> traversal) {
if (node != null && !isLeaf(node)) {
traversal.add(node.getData());
preorderTraversal(node.getLeft(), traversal);
preorderTraversal(node.getRight(), traversal);
} else if (node != null && isLeaf(node)) {
traversal.add(node.getData());
}
return traversal;
}
@Override
public List<T> postorder() {
// left, right, node; base: if leaf
LinkedList<T> traversal = new LinkedList<>();
return postorderTraversal(root, traversal);
}
/**
* Recursive helper method to traverse through the tree, saving each
* particular node to a list.
* Postorder Traversal is defined as marking Node.left, Node.right, Node in
* that order.
*
* @param node the node being traversed through currently
* @param traversal the list that the nodes are recorded in
* @return the list of all visited nodes
*/
private List<T> postorderTraversal(BSTNode<T> node, List<T> traversal) {
if (node != null && !isLeaf(node)) {
postorderTraversal(node.getLeft(), traversal);
postorderTraversal(node.getRight(), traversal);
traversal.add(node.getData());
} else if (node != null && isLeaf(node)) {
traversal.add(node.getData());
}
return traversal;
}
@Override
public List<T> inorder() {
// left, node, right; base: is leaf
LinkedList<T> traversal = new LinkedList<>();
return inorderTraversal(root, traversal);
}
/**
* Recursive helper method to traverse through the tree, saving each
* particular node to a list.
* Inorder Traversal is defined as marking Node.left, Node, Node.right in
* that order.
*
* @param node the node being traversed through currently
* @param traversal the list that the nodes are recorded in
* @return the list of all visited nodes
*/
private List<T> inorderTraversal(BSTNode<T> node, List<T> traversal) {
if (node != null && !isLeaf(node)) {
inorderTraversal(node.getLeft(), traversal);
traversal.add(node.getData());
inorderTraversal(node.getRight(), traversal);
} else if (node != null && isLeaf(node)) {
traversal.add(node.getData());
}
return traversal;
}
@Override
public List<T> findPathBetween(T data1, T data2) {
if (data1 == null || data2 == null) {
throw new IllegalArgumentException(“Input data is null, please”
+ ” use a non-null input.”);
}
List<T> path = new LinkedList<>();
if (data1.equals(data2)) {
path.add(data1);
} else {
BSTNode<T> dca = findCommonAncestor(data1, data2, root);
path = findFirstLeg(data1, dca, path);
path = findSecondLeg(data2, dca, path);
}
return path;
}
/**
* Recursive helper method to find the first half of the path between
* two nodes. This path is from data1 to the Deepest Common Ancestor (DCA),
* adding all the nodes to data1 to the front of the list.
*
* @param data the data to which the path is made
* @param node the node being searched through currently
* @param path the continuously growing path to the data
* @throws NoSuchElementException if the data is not found in the tree
* @return the list of all nodes between the DCA and the data, excluding
* the DCA, as it will be entered in during the second half
*/
private List<T> findFirstLeg(T data, BSTNode<T> node, List<T> path) {
// Traverse to data1 adding nodes along the way to the front
if (node != null) {
if (data.compareTo(node.getData()) == 0) {
((LinkedList<T>) path).addFirst(node.getData());
// Since inevitably the DCA was added, remove it since
// it will also be added in the second leg – O(1)
((LinkedList<T>) path).removeLast();
// This is the end of the search
return path;
} else if (data.compareTo(node.getData()) > 0) {
((LinkedList<T>) path).addFirst(node.getData());
return findFirstLeg(data, node.getRight(), path);
} else {
((LinkedList<T>) path).addFirst(node.getData());
return findFirstLeg(data, node.getLeft(), path);
}
}
throw new NoSuchElementException(“One or more of the given inputs”
+ ” is not contained in this tree.”);
}
/**
* Recursive helper method to find the second half of the path between
* two nodes. This path is from data2 to the Deepest Common Ancestor (DCA),
* adding all the nodes to data2 to the back of the list.
*
* @param data the data to which the path is made
* @param node the node being searched through currently
* @param path the continuously growing path to the data
* @throws NoSuchElementException if the data is not found in the tree
* @return the list of all nodes between the DCA and the data, including
* the DCA
*/
private List<T> findSecondLeg(T data, BSTNode<T> node, List<T> path) {
// Traverse to data2 adding nodes along the way to the back
if (node != null) {
if (data.compareTo(node.getData()) == 0) {
((LinkedList<T>) path).addLast(node.getData());
// This is the end of the search
return path;
} else if (data.compareTo(node.getData()) > 0) {
((LinkedList<T>) path).addLast(node.getData());
return findSecondLeg(data, node.getRight(), path);
} else {
((LinkedList<T>) path).addLast(node.getData());
return findSecondLeg(data, node.getLeft(), path);
}
}
throw new NoSuchElementException(“One or more of the given inputs”
+ ” is not contained in this tree.”);
}
/**
* Recursive helper method to determine the Deepest Common Ancestor (DCA)
* of data1 and data2.
* The DCA is defined as the lowest node in the tree that possesses both
* data1 and data2 as children in its subtree.
*
* @param data1 the first data input (can be less than data2)
* @param data2 the second data input (can be less than data1)
* @param node the node being searched through currently
* @return the node for the Deepest Common Ancestor
*/
private BSTNode<T> findCommonAncestor(T data1, T data2, BSTNode<T> node) {
// Traverse to DCA once
if (data1.compareTo(data2) < 0) {
// d1 < DCA < d2
if (node.getData().compareTo(data1) >= 0
&& node.getData().compareTo(data2) <= 0) {
// DCA found
return node;
} else if (node.getData().compareTo(data1) < 0) {
return findCommonAncestor(data1, data2, node.getRight());
} else {
return findCommonAncestor(data1, data2, node.getLeft());
}
} else {
// d2 < DCA < d1
if (node.getData().compareTo(data2) >= 0
&& node.getData().compareTo(data1) <= 0) {
// DCA found
return node;
} else if (node.getData().compareTo(data2) < 0) {
return findCommonAncestor(data1, data2, node.getRight());
} else {
return findCommonAncestor(data1, data2, node.getLeft());
}
}
}
@Override
public void clear() {
root = null;
size = 0;
}
@Override
public int height() {
if (isEmpty()) {
return -1;
} else {
return nodeHeight(root);
}
}
/**
* Recursive helper method for determining the height of any node.
* A node’s height is defined as {@code max(left.height, right.height) + 1}.
* A leaf node has a height of 0. Calculated in O(n).
*
* @param node the node in question
* @return the height of that node
*/
private int nodeHeight(BSTNode<T> node) {
if (node == null || isLeaf(node)) {
return 0;
} else {
return Math.max(nodeHeight(node.getLeft()),
nodeHeight(node.getRight())) + 1;
}
}
/**
* Determines whether the BST is empty, which is defined as the tree
* having a size of 0.
*
* @return whether the BST is empty
*/
private boolean isEmpty() {
return size == 0;
}
/**
* Determines whether then input node is an internal or external node.
* An external node, or leaf, is defined as having no children; that is,
* the input node has neither a left nor a right child.
*
* @param node the node in question
* @return whether the input node is a leaf or not
*/
private boolean isLeaf(BSTNode<T> node) {
return node.getLeft() == null && node.getRight() == null;
}
@Override
public BSTNode<T> getRoot() {
return root;
}
}
BSTInterface.java
import java.util.List;
public interface BSTInterface<T extends Comparable<? super T>> {
/**
* Add the data as a leaf in the BST. Should traverse the tree to find the
* appropriate location. If the data is already in the tree, then nothing
* should be done (the duplicate shouldn’t get added, and size should not be
* incremented).
* Should have a running time of O(log n) for a balanced tree, and a worst
* case of O(n).
*
* @throws IllegalArgumentException if the data is null
* @param data the data to be added
*/
void add(T data);
/**
* Removes the data from the tree. There are 3 cases to consider:
*
* 1: the data is a leaf. In this case, simply remove it.
* 2: the data has one child. In this case, simply replace it with its
* child.
* 3: the data has 2 children. There are generally two approaches:
* replacing the data with either the largest element that is smaller than
* the element being removed (commonly called the predecessor), or replacing
* it with the smallest element that is larger than the element being
* removed (commonly called the successor). For this assignment, use the
* predecessor. You may use iteration to find the predecessor AFTER you have
* found the node to be removed recursively (but don’t start back at the
* root to do so).
*
* Should have a running time of O(log n) for a balanced tree, and a worst
* case of O(n).
*
* @throws IllegalArgumentException if the data is null
* @throws java.util.NoSuchElementException if the data is not found
* @param data the data to remove from the tree.
* @return the data removed from the tree. Do not return the same data
* that was passed in. Return the data that was stored in the tree.
*/
T remove(T data);
/**
* Returns the data in the tree matching the parameter passed in (think
* carefully: should you use .equals or == ?).
* Should have a running time of O(log n) for a balanced tree, and a worst
* case of O(n).
*
* @throws IllegalArgumentException if the data is null
* @throws java.util.NoSuchElementException if the data is not found
* @param data the data to search for in the tree.
* @return the data in the tree equal to the parameter. Do not return the
* same data that was passed in. Return the data that was stored in the
* tree.
*/
T get(T data);
/**
* Returns whether or not the parameter is contained within the tree.
* Should have a running time of O(log n) for a balanced tree, and a worst
* case of O(n).
*
* @throws IllegalArgumentException if the data is null
* @param data the data to search for in the tree.
* @return whether or not the parameter is contained within the tree.
*/
boolean contains(T data);
/**
* Should run in O(1).
*
* @return the number of elements in the tree
*/
int size();
/**
* Should run in O(n).
*
* @return a preorder traversal of the tree
*/
List<T> preorder();
/**
* Should run in O(n).
*
* @return a postorder traversal of the tree
*/
List<T> postorder();
/**
* Should run in O(n).
*
* @return an inorder traversal of the tree
*/
List<T> inorder();
/**
* 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<T> findPathBetween(T data1, T data2);
/**
* Clear the tree. Should be O(1).
*/
void clear();
/**
* Calculate and return the height of the root of the tree. A node’s
* height is defined as {@code max(left.height, right.height) + 1}. A leaf
* node has a height of 0.
* Should be calculated in O(n).
*
* @return the height of the root of the tree, -1 if the tree is empty
*/
int height();
/**
* THIS METHOD IS ONLY FOR TESTING PURPOSES.
* DO NOT USE IT IN YOUR CODE
* DO NOT CHANGE THIS METHOD
*
* @return the root of the tree
*/
BSTNode<T> getRoot();
}
BSTNode.java
public class BSTNode<T extends Comparable<? super T>> {
private T data;
private BSTNode<T> left;
private BSTNode<T> 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<T> getLeft() {
return left;
}
/**
* Set the node to the left of this node.
*
* @param left new node to the left.
*/
public void setLeft(BSTNode<T> left) {
this.left = left;
}
/**
* Get the node to the right of this node.
*
* @return node to the right.
*/
public BSTNode<T> getRight() {
return right;
}
/**
* Set the node to the right of this node.
*
* @param right new node to the right.
*/
public void setRight(BSTNode<T> right) {
this.right = right;
}
}
