3. BST

• In this lab you will start implementing your own data structure library.

• You will implement the following UML in Java:

3.1. BST - Start

1. Create a package trees.

2. Create the interface SearchTree.

3.2. BST - BinaryTree

1. Create the structure of the generic class BinaryTree.

   • It should implement Serializable.

2. Create the generic and static class Node.

   • It should implement Serializable.

   • It contains only three data fields.

   • Implement the constructor Node(E data).

   • Implement the method toString().

3. Now finish the class BinaryTree.

   • You will implement three constructors:

     • BinaryTree()

     • BinaryTree(Node<E> root)

     • BinaryTree(E data, BinaryTree<E> leftTree, BinaryTree<E> rightTree)

3.3. BST - BinaryTreeSearch

1. Create the generic class BinarySearchTree.

   • The generic type E should inherit from Comparable.

   • The class should inherit from BinaryTree.

   • And it should implement SearchTree

2. Implement all the function from the interface.

3. Make sure that your code works.

3.4. LeetCode

If you are done, you can start doing the following problems on LeetCode:

• https://leetcode.com/problems/binary-tree-inorder-traversal/

• https://leetcode.com/problems/subtree-of-another-tree/

• https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/

• https://leetcode.com/problems/unique-binary-search-trees/