depthInTree()

The recursive depthInTree() method takes two parameters – an integer key and the root of a tree/subtree – and it returns the depth in that tree/subtree of the node with the specified key. It is a private static method that can only be called from within the class.

The separate depth() method is a “wrapper” method that makes the initial call to depthInTree(), passing in the root of the tree as a whole and returning whatever value depthInTree() returns – which will be the depth in the entire tree of the node with the specified key.

If the key is not found, the methods return -1.

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;
}
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.