Binary Search Tree

Develop class BinarySearchTree (BST) as a generic collection that stores any number of nodes in a binary search tree data structure. Each node has a reference to data, a left binary search tree, and a right binary search tree. The type to be stored must be limited to types that implement the Comparable interface or any interface that extends Comparable.

publicclass BinarySearchTree<E extends Comparable<E> {

The required method headings are provided below with their behavior listed as comments. Check our Code Demos page for a start to this class store as BinarySearchTree.java that has the first four methods implemented already: insert, sideways, remove, height. Also feel free to use the beginning of the unit test BinarySearchTreeTest.java.

// Add element to this BST and return true keeping this a BST. If element is found

// to already exist, do not change this BST, simply return false.

publicboolean insert(E element)

// If element equals an element in this BST, remove it and return true. Return false

// whenever element is not found. In all cases, this BST must remain a true BST.

// Here is one algorithm for removing from a BST: BSTRemoveGeneric.pdf

publicboolean remove(E element)

// Return one string that concatenates the toString() version of all elements in

// this BST as they are visited with a reverse inOrder traversal. All data are

// preceded by one string "- " for each level on which the node resides. A tree with

// inserts of the integers 40 80 60 100 20 10 would like this sideways:

// - - 99

// - 80

// - - 60

// 40

// - 20

// - - 10

public String toStringSideways(E element)

// The longest path in this BST beginning at the root.

// Note: An empty tree has a height of -1.

publicint height()

Add the following methods. Test them well before WebCat turnin.

// The number of elements in this BST, which is 0 when first constructed.

// This may run O(n)

publicint size()

// Return a String that concatenates the toString() version of all elements

// in this BST as they are traversed preOrder. A tree that looks like this after

// 4 1, and 9 are inserted would have toStringPreorder return all elements

// separated by spaces as "4 1 9"

// 4

// / \

// 1 9

public String toStringPreorder()

// Return a String that concatenates the toString() version of all elements in a BST

// as they are traversed postOrder. A tree that looks like this after 4 1, and 9 are

// inserted would have toStringPostorder return all elements separated by spaces

// as "1 9 4"

// 4

// / \

// 1 9

public String toStringPostorder()

// Return true if search "equals" an element in this BST.

// Return false is search is not found.

publicboolean contains(E search)

// Return an array that has capacity equal to this BST's size with the

// minimum value at index 0 and the maximum value at index array length-1

public Object[] toArray()

// Return the element in this BST that is greater than all other elements.

// If this BST is empty, return null.

public E max()

// Return the number of leafs in this BST. Note: An empty tree has 0 leafs.

publicint numberOfLeafs()

// Return true if this BST is empty or every node has exactly two children or is a leaf

// This tree is not full so isFull would return false after insertions of 5 and 2.

// 5

// /

// 2

publicboolean isFull()

// Return true if two different BSTs have the same exact structure. Empty trees have

// the same structure. These two do also (Note: the data do not need to be equal):

// M P

// / \ / \

// B R F Q

// \ \ \ \

// F Z J R

// Precondition: E is the same for both BSTs

publicboolean sameStructure(BinarySearchTree<E> other)

// Return how many nodes are on the given level. In the following tree, level 0 has 1

// node, level 1 has two nodes, level 2 has four, and levels >= 3 have zero nodes.

// M

// / \

// B R

// / \ / \

// A F P Z

publicint nodesAtLevel(int level)

Grading Criteria

100 pts for WebCat Problem and Code coverage