12. Given the BinarySearchTree class, write the instance method add (and any sup
ID: 3707632 • Letter: 1
Question
12. Given the BinarySearchTree class, write the instance method add (and any supporting recursive methods), which will add the given Comparable element into the BST public class BSTNodecT private T info; private BSTNode right; private BSTNode left; public class BinarySearchTree implements Iterator public BSTNode(T info this.info info; BSTNode root = null; public T getlnfo)(.. public void setinfo(T info) (.. public BSTNode getRight) (..) public void setRight(BSTNode node) public BSTNodecT> getLeft) (.) public void setLeft(BSTNode node) public void add (T element) fExplanation / Answer
public class BinarySearchTree<T extends Comparable<T>>
{
BSTNode<T> root;
private Comparator<T> comparator;
/**
* constructor create a empty binary search tree by setting root to be null
*/
public BinarySearchTree(){
root = null;
}
private int compare(T x, T y)
{
if(comparator == null)
return x.compareTo(y);
return comparator.compare(x,y);
}
/**
* Insert given node to this binary search tree. If this tree
* is empty, the given node becomes the root of this tree.
* @param newNode the given node to be inserted
*/
public void add(T element)
{
// getData() return the value of node
this.root = insert_util( this.root , element );
}
private BSTNode<E> insert_util(BSTNode<T> node, T data)
{
// if tree is empty
if (node == null)
// create a new node
node = new BSTNode<T>(data);
// if the dats lies in the right subtree
else if (compare(node.getData(), data) < 0)
node.setRight(insert_util(node.getRight(), data));
// if the dats lies in the left subtree
else
node.setLeft(insert_util(node.getLeft(), data));
return node;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.