2. (10) In a BST with n nodes, what is the time complexity forsearching, insertion, and deletion in worst case, respectively?What is the time complexity for these operation in average case(balanced tree), respectively?
3. (30) Modify program BinarySearchTree.java by adding thefollowing operations to the BinarySearchTree class:

1. Find the height of the BST.
2. Find node with the smallest key.
3. Find the average of the key values of the nodes.
4. Create the same BST shown in question 1. Run your program forthe BST to its final state and output the height, the smallest key,and average of the keys.

Submit code and running screenshots.

Question 1

(20) Assume that a binary search tree BST of integer is created.First, we call insert 10 times to insert integers 11, 22, 15, 44,6, 9, 3, 33, 17, 5 into the BST in that order; then we call delete2 times to delete the nodes with 13, 22 from the BST, respectively;finally we call insert again to insert 18 into the BST.

Answer rating: 100% (QA)

1 Time Complexity in Binary Search Trees BST Worst Case Searching On If the tree is completely unbal... View the full answer