public int depth(int key) { if (root == null) { // root is the root of the entire tree return -1; } return depthInTree(key, root); } private static int depthInTree(int key, Node root) { if (key == root.key) { return 0; } if (root.left != null) { int depthInLeft = depthInTree(key, root.left); if (depthInLeft != -1) { return depthInLeft + 1; } } if (root.right != null) { int depthInRight = depthInTree(key, root.right); if (depthInRight != -1) { return depthInRight + 1; } } return -1; }

1. For a binary tree with n nodes, what is the time complexity of this algorithm as a function of n in the best case? In the worst case? For the worst case, give two expressions: one for when the tree is balanced, and one for when the tree is not balanced. Give your answers using big-O notation, and explain them briefly.

2. If the tree is a binary search tree, we can revise the algorithm to take advantage of the ways in which the keys are arranged in the tree. Write a revised version of depthInTreethat does so. Your new method should avoid considering subtrees that couldnt contain the specified key. Like the original version of the method above, your revised method should be recursive.

Note: In the files that weve given you for Part II, the LinkedTree class includes the methods shown above. Feel free to replace the original depthInTree() method with your new version so that you can test its correctness. However, your new version of the method should ultimately be included in your ps7pr4.txt file.

3. For a binary search tree with n nodes, what is the time complexity of your revised algorithm in the best case? In the worst case? For the worst case, give two expressions: one for when the tree is balanced, and one for when the tree is not balanced. Give your answers using big-O notation, and explain them briefly.