DESCRIPTION In this lab you will implement the Set abstract data type using binary search trees. We will consider sets of integers where each integer will be stored in a tree node. Therefore the number of nodes in the binary search tree must be equal to the size of the set. You will have to write a Java class BSTSet for this purpose. To implement the tree nodes you must use the Java class TNode provided in this lab. Additionally, you may need to implement Java classes MyStack and/or MyQueue to perform non-recursive tree traversals of a BSTSet. You are not permitted to use any predefined Java methods or classes from Java API, other than for input and output, unless specified otherwise You must also write a test class TestBSTSet. Please compute the asymptotic run time and space complexity of a methods and be ready to present them to the TA with explanations at your demo. DEFINITIONS: A set is an unordered collection of elements with no repetition. Examples are the set of real numbers, the set of integer numbers or the set consisting of numbers 1,2,30 For this lab we will only be considering representing finite sets consisting of elements which are integers. Examples: 0,34,78, 1000), 14,5, 890, 65535), 10, 1,2,. ,65534, 65535, are all valid sets. The union of two sets, say A and B, is written as AUB and is the set which contains all of the elem ents in either A or B or both. Example: If A {3, 8, 14, 15) and B-12, 8, 9, 15, 1001, then A u B = {2,3, 8, 9, 14, 15, 100)(notice that there are no repeated elements in a set) . The intersection of two sets A and B is written as AnB and is the set which contains the elements that are common to A and B. Examples: If A = {3,8, 14, 15) and B = 12, 8, 9, 15, 1001, then An B-8, 15). If A = {17, 20.38) and B = {2001, then A n B = {}, which is termed the empty set. SPECIFICATIONS: You must use the Java class TNode given below, to implement the tree nodes. Classes TNode and BSTSet must be contained in the same package public class TNodef int element TNode left; TNode right; TNode(int i, TNode 1, TNode r) DESCRIPTION In this lab you will implement the Set abstract data type using binary search trees. We will consider sets of integers where each integer will be stored in a tree node. Therefore the number of nodes in the binary search tree must be equal to the size of the set. You will have to write a Java class BSTSet for this purpose. To implement the tree nodes you must use the Java class TNode provided in this lab. Additionally, you may need to implement Java classes MyStack and/or MyQueue to perform non-recursive tree traversals of a BSTSet. You are not permitted to use any predefined Java methods or classes from Java API, other than for input and output, unless specified otherwise You must also write a test class TestBSTSet. Please compute the asymptotic run time and space complexity of a methods and be ready to present them to the TA with explanations at your demo. DEFINITIONS: A set is an unordered collection of elements with no repetition. Examples are the set of real numbers, the set of integer numbers or the set consisting of numbers 1,2,30 For this lab we will only be considering representing finite sets consisting of elements which are integers. Examples: 0,34,78, 1000), 14,5, 890, 65535), 10, 1,2,. ,65534, 65535, are all valid sets. The union of two sets, say A and B, is written as AUB and is the set which contains all of the elem ents in either A or B or both. Example: If A {3, 8, 14, 15) and B-12, 8, 9, 15, 1001, then A u B = {2,3, 8, 9, 14, 15, 100)(notice that there are no repeated elements in a set) . The intersection of two sets A and B is written as AnB and is the set which contains the elements that are common to A and B. Examples: If A = {3,8, 14, 15) and B = 12, 8, 9, 15, 1001, then An B-8, 15). If A = {17, 20.38) and B = {2001, then A n B = {}, which is termed the empty set. SPECIFICATIONS: You must use the Java class TNode given below, to implement the tree nodes. Classes TNode and BSTSet must be contained in the same package public class TNodef int element TNode left; TNode right; TNode(int i, TNode 1, TNode r)
