Pls implement following methods into BinarySearchTree.java

here are method need to be completed:

insert inserts a specified key into the BinarySearchTree object. Duplicate keys will not be allowed. Inserting must be completed iteratively.

remove removes the specified key from the BinarySearchTree object, using the proper (non-lazy) method described in the lecture slides. The method returns false if the key is not found. Complete the code for the recursive method remove(BSTNode nd, int item) that is called by the remove(int item) method. Use the predecessor replacement rule for the 2-child case.

size calculates the number of keys in the BinarySearchTree object.

height this method recursively calculates the height of the (sub)tree rooted at its parameter. Think about how the height of a node is calculated, when you know the heights of both subtrees. Math.max(a,b) returns the maximum of a and b.

countEvenNumbers returns the number of even numbers in the BinarySearchTree object.

contains tests and returns true if a specified key is present in the BinarySearchTree object, false otherwise.

isAVLTree returns true, if the BinarySearchTree object is an AVL tree, i.e. for each node the height difference between left and right subtree is at most 1. printDescending recursively prints all numbers of the BinarySearchTree object in descending order.

toArray creates an ascendingly ordered array of all keys in the BinarySearchTree object. Use a flexible ArrayList object first, then convert it to a fixed sized array to be returned.

join adds all (non-duplicate) key values of another BinarySearchTree object specified as parameter to the existing BinarySearchTree object.

here is BinarySearchTree.java:

import java.util.ArrayList;

class BSTNode {

//public member attributes

// direct access for simplicity

public int data;

public BSTNode left, right;

// Default/leaf node constructor

public BSTNode(int value){

data = value;

left = null;

right = null;

}

}

public class BinarySearchTree {

private BSTNode root;

// default constructor

public BinarySearchTree() {

root = null;

}

// Inserts a new leaf node while maintaining BST properties

// Should be completed iteratively in this method,

// do not allow duplicates.

public void insert(int item){

// to be completed: the iterative version

BSTNode newNode = new BSTNode(item);

}

// returns false if item is not in the tree

// removes and returns true if item can be found and removed

public boolean remove(int item){

int oldSize = getSize();

root = remove(root, item);

return (oldSize-1 == getSize());

}

// Recursive remove, returns the root of the subtree after removal.

// Control the special cases

// - removing root

// - removing the only node in the tree.

// Use the predecessor strategy for the 2-child case

private BSTNode remove(BSTNode nd, int item){

if (nd == null) // base case: item not found

return null;

else{

if (item < nd.data) // item is in the left subtree

nd.left = remove(nd.left, item);

else if (item > nd.data) // item is in the right subtree

nd.right = remove(nd.right, item);

else{ // item found & to be removed here

// to be completed : The three removal cases as discussed in class

}

return nd;

}

}

// returns the number of items stored in the tree

public int getSize(){

return size(root);

}

private int size(BSTNode nd){

// to be completed

return 0;

}

// returns the height of the tree

// an empty tree has height -1

// a tree of only the root has height 0

public int getHeight(){

return height(root);

}

// Recursively computes the height of a subtree rooted at nd

// Use Math.max to choose the taller of nd's two children

// the height of an empty tree is -1.

private int height(BSTNode nd){

// to be completed

return 0;

}

// Search function

// Returns true if the search term is in the tree, false otherwise

// May be implemented iteratively in this function, or recursively

// using your own private helper function

public boolean contains(int item){

return contains(root, item);

}

// recursive contains method

private boolean contains(BSTNode nd, int item){

// to be completed

return false;

}

public int countEvenNumbers(){

return countEvenNumbers(root);

}

private int countEvenNumbers(BSTNode nd){

// to be completed

return 0;

}

public boolean isAVLTree(){

return isAVLTree(root);

}

private boolean isAVLTree(BSTNode nd){

// to be completed, without changing the BSTNode class!

return true;

}

public void printDescending(){

printDescending(root);

}

private void printDescending(BSTNode nd){

// to be completed

}

public int[] toArray(){

int[] arr = new int[getSize()];

return arr;

}

public void join(BinarySearchTree2 otherBST){

// to be completed

BSTNode otherRoot=otherBST.root;

}

// Calls the recursive method for printing a tree sideways.

public void printTreeSideways(){

printTreeSideways(root,0);

}

// recursively prints the contents/structure of the tree,

// rotated counter-clockwise 90 degrees.

// parameter: the number of tab characters to insert

// example output: for a tree with root 12, left child 5, right child 17

// print the following tree structure:

// 17

// 12

// 5

private void printTreeSideways(BSTNode nd, int level){

if (nd != null){

printTreeSideways(nd.right, level+1);

for (int i=1; i<= level; i++)

System.out.print("\t");

System.out.println(nd.data);

printTreeSideways(nd.left, level+1);

}

}

}