public class BinarySearchTree >

{

private BSTNode root;

private int size;

public BinarySearchTree()

{

root = null;

size = 0;

}

public int Size()

{

return size;

}

/* ***************************************************************

* Insert a new node

* Returns true on successful insert otherwise false (when already present)

*****************************************************************/

public boolean insert(T data)

{

//TODO -> implement here

return false;

}

/*****************************************************************

* Delete a node

* Returns true on successful deletion and false otherwise

*****************************************************************/

public boolean delete(T data)

{

boolean found = false;

//TODO -> Implement here

return found;

}

/****************************************************************

*

* Reset Tree

*

***************************************************************/

public void reset()

{

root = null;

size=0;

}

/*****************************************************************

*

* Height of tree

*

****************************************************************/

public int height()

{

//TODO -> Implement here

return 0;

}

/*****************************************************************

*

* Traversal

*

******************************************************************/

public void inorder()

{

System.out.print("inorder BST: ");

//TODO -> Implement here (print all nodes)

System.out.println();

}

public void preorder()

{

System.out.print("preorder BST: ");

//TODO -> Implement here

System.out.println();

}

public void postorder()

{

System.out.print("postorder BST: ");

//TODO -> Implement here

System.out.println();

}

}

__________________________________________________________________

package SearchTrees;

import java.util.*;

public class SearchTreeTesting {

public static void main(String[] args)

{

BinarySearchTree bst = new BinarySearchTree();

RedBlackTree rbt = new RedBlackTree();

// Generate 1000 random numbers between 1 and 10000

HashSet randomNumberSet = new HashSet<>();

Random rand = new Random();

int randInt;

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

{

do{

randInt = rand.nextInt(10000);

}while (randomNumberSet.contains(randInt));

randomNumberSet.add(randInt);

}

System.out.println("***********Random Input Case****************");

System.out.println();

// Insert the numbers generated into the binary search tree

// Calculate the total time for insertion and print it

Iterator iter = randomNumberSet.iterator();

long startTime = System.currentTimeMillis();

while (iter.hasNext())

{

bst.insert((Integer)iter.next());

}

long endTime = System.currentTimeMillis();

long executionTime = endTime - startTime;

System.out.println("Size of the BST = "+bst.Size());

System.out.println("Height of the BST = "+bst.height());

System.out.println("Time to insert in BST = "+ executionTime);

bst.inorder();

System.out.println();

System.out.println();

// Insert the numbers generated into the redblack tree

// Calculate the total time for insertion and print it

iter = randomNumberSet.iterator();

startTime = System.currentTimeMillis();

while (iter.hasNext())

{

rbt.insert((Integer)iter.next());

}

endTime = System.currentTimeMillis();

executionTime = endTime - startTime;

System.out.println("Size of the RBT = "+rbt.Size());

System.out.println("Height of the RBT = "+rbt.height());

System.out.println("Time to insert in RBT = "+ executionTime);

rbt.inorder();

System.out.println();

System.out.println();

// Delete all the nodes in the binary search tree

// Calculate the total time for deletion and print it

iter = randomNumberSet.iterator();

startTime = System.currentTimeMillis();

while (iter.hasNext())

{

bst.delete((Integer)iter.next());

}

endTime = System.currentTimeMillis();

executionTime = endTime - startTime;

System.out.println("Size of the BST = "+bst.Size());

System.out.println("Height of the BST = "+bst.height());

System.out.println("Time to delete in BST = "+ executionTime);

bst.inorder();

System.out.println();

System.out.println();

// Delete all the nodes in the red black tree

// Calculate the total time for deletion and print it

iter = randomNumberSet.iterator();

startTime = System.currentTimeMillis();

while (iter.hasNext())

{

rbt.delete((Integer)iter.next());

}

endTime = System.currentTimeMillis();

executionTime = endTime - startTime;

System.out.println("Size of the RBT = "+rbt.Size());

System.out.println("Height of the RBT = "+rbt.height());

System.out.println("Time to delete in RBT = "+ executionTime);

rbt.inorder();

System.out.println();

System.out.println();

System.out.println("***********Sorted Input Case****************");

System.out.println();

bst.reset();

rbt.reset();

// Insert 1000 sorted numbers(1 to 1000) into the binary search tree

// Calculate the total time for insertion and print it

startTime = System.currentTimeMillis();

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

{

bst.insert(i);

}

endTime = System.currentTimeMillis();

executionTime = endTime - startTime;

System.out.println("Size of the BST = "+bst.Size());

System.out.println("Height of the BST = "+bst.height());

System.out.println("Time to insert in BST = "+ executionTime);

bst.inorder();

System.out.println();

System.out.println();

// Insert 1000 sorted numbers(1 to 1000) into the red black tree

// Calculate the total time for insertion and print it

startTime = System.currentTimeMillis();

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

{

rbt.insert(i);

}

endTime = System.currentTimeMillis();

executionTime = endTime - startTime;

System.out.println("Size of the RBT = "+rbt.Size());

System.out.println("Height of the RBT = "+rbt.height());

System.out.println("Time to insert in RBT = "+ executionTime);

rbt.inorder();

System.out.println();

System.out.println();

// Delete all the nodes in the binary search tree

// Calculate the total time for deletion and print it

startTime = System.currentTimeMillis();

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

{

bst.delete(i);

}

endTime = System.currentTimeMillis();

executionTime = endTime - startTime;

System.out.println("Size of the BST = "+bst.Size());

System.out.println("Height of the BST = "+bst.height());

System.out.println("Time to delete in BST = "+ executionTime);

bst.inorder();

System.out.println();

System.out.println();

// Delete all the nodes in the red black tree

// Calculate the total time for deletion and print it

startTime = System.currentTimeMillis();

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

{

rbt.delete(i);

}

endTime = System.currentTimeMillis();

executionTime = endTime - startTime;

System.out.println("Size of the RBT = "+rbt.Size());

System.out.println("Height of the RBT = "+rbt.height());

System.out.println("Time to delete in RBT = "+ executionTime);

rbt.inorder();

System.out.println();

System.out.println();

}

}

1. Implement the following methods in class BinarySearchTree. For all these methods you just

need to implement the body of the methods already present in the class,

a. Insert: This method inserts a node in the binary search tree. This method must

increment size variable after successful insertion.

b. Delete: this method deletes a node in the binary search tree. This method must

decrement size variable after successful deletion.

c. Height: this method returns the height of the binary search tree

d. Traversal methods: should print the values of the node traversed

i. Inorder: for in-order traversal

ii. Preorder: for pre-order traversal

iii. Postorder: for post-order traversal