(Solved): In this assignment, you will be creating a binary search tree (BST). The tree will be storing words ...

In this assignment, you will be creating a binary search tree (BST). The tree will be storing words ( Strings). You will need to define a BSTNode class, which is similar to the Node class you implemented in previous lectures. BSTNode will be used to store an item of type String. It will also contain references to its left and right subtrees. The BSTNode constructor will initialize the item to a value and the left and right nodes to null. BSTNode should be defined as an inner class inside of BinarySearchTree . The fields of BSTNode are: ? String item ? BSTNode left ? BSTNode right The BinarySearchTree class itself only has one field, the root of the BST. The constructor for the BinarySearchTree only has to set the root to null . We will be using a Queue to store elements from traversals. That is, instead of preorder, inorder and postorder traversals printing out the elements of the tree, they will each return a Queue containing the elements in that order. You can use The Queue class implemented in previous lectures or just use the Queue class from the java library. You will be implementing the following methods for your BST: ? public boolean isEmpty () Returns true if BST is empty, false otherwise ? public Queue inOrder () Returns a queue with the elements in-order 2 ? public Queue preOrder () Returns a queue with the elements in pre-order ? public Queue postOrder () Returns a queue with the elements in post-order ? public boolean contains (String s) Returns true if the BST contains the string, otherwise returns false.

In this assignment, you will be creating a binary search tree (BST). The tree will be storing words (Strings) You will need to define a BSTNode class, which is similar to the Node class you implemented in previous lectures. BSTNode will be used to store an item of type String. It will also contain references to its left and right subtrees. The BSTNode constructor will initialize the item to a value and the left and right nodes to null. BSTNode should be defined as an inner class inside of Binary Search Tree. The fields of BSTNode are: • String item • BSTNode left • BSTNode right The Binary Search Tree class itself only has one field, the root of the BST. The constructor for the Binary Search Tree only has to set the root to null. We will be using a Queue to store elements from traversals. That is, instead of preorder, inorder and postorder traversals printing out the clements of the tree, they will each return a Queue containing the elements in that order. You can use The Queue class implemented in previous lectures or just use the Queue class from the java library You will be implementing the following methods for your BST: • public boolean isEmpty o Returns true if BST is empty, false otherwise . public Queue inOrder 0 Returns a queue with the elements in order 1 • public Queue preOrdero Returns a queue with the elements in pre-order public Queue postOrder o Returns a queue with the elements in post-order . public boolean contains (Strings) Returns true if the BST contains the string, otherwise return false