Description
Question 1 Create a package called BST and implement a node class called TreeNode and Binary Search Tree Class called BST. Both the BST and TreeNode classes extends Comparable. a) Include necessary declaration in the BST and TreeNode classes. b) Implement the following methods in class BST: i. public boolean search(E e) Returns true if the element is in the tree ii. public boolean insert(E e) Insert element o into the binary tree and return true if the element is inserted successfully iii. public int getSize() Get the number of nodes in the tree iv. public int height()and private int height(TreeNode node) Returns the height of the BST v. public E getRoot() Returns the root of the BST vi. public E minValue() Returns the minimum value of the BST vii. public E maxValue() Returns the maximum value of the BST viii. public java.util.ArrayList<TreeNode> path(E e) Returns a path from the root leading to the specified element ix. public boolean delete(E e) Delete an element from the binary tree. Return true if the element is deleted successfully, and return false if the element is not in the tree x. public boolean clear() Remove all elements from the tree WIA1002/WIB1002 Lab 11 Sem. 2, 2018/2019 Page 2 xi. protected void inorder(TreeNode root) Display inorder traversal from a subtree xii. protected void postorder(TreeNode root) Display postorder traversal from a subtree xiii. protected void preorder(TreeNode root) Display preorder traversal from a subtree c) Write a test program called TestBST in the BST package. Using the appropriate methods you implemented in BST, produce the following output: Input Data: 45, 88, 54, 76, 98, 1, 2, 20, 6, 53, 42, 100, 86, 32, 28, 65, 14 Inorder (sorted): 1 2 6 14 20 28 32 42 45 53 54 65 76 86 88 98 100 Postorder: 14 6 28 32 42 20 2 1 53 65 86 76 54 100 98 88 45 Preorder: 45 1 2 20 6 14 42 32 28 88 54 53 76 65 86 98 100 Height of BST: 6 Root for BST is: 45 Check whether 10 is in the tree? false Delete 53 Updated Inorder data (sorted): 1 2 6 14 20 28 32 42 45 54 65 76 86 88 98 100 Min Value :1 Max Value :100 A path from the root to 6 is: 45 1 2 20 6