Time and space complexity of this function to print binary tree level by level

Question

This algorithm is for printing a common binary tree level by level.

What is the time complexity and space complexity of printSpecificLevel_BT() and printBT_LBL()?

I think printSpecificLevel_BT's time complexity is O(lg N), and space complexity is O(lg N).
I think printBT_LBL()'s time complexity is O((lgN)^2), and the space complexity is O((lgN)^2).

Is this correct?

// Print the specific level of a binary tree.
public static void printSpecificLevel_BT (Node root, int level) {
    if (root == null) return;
    if (level == 0) System.out.print(String.format("%-6d", root.data)); // Base case.
    // Do recrusion.
    printSpecificLevel_BT(root.leftCh, level - 1);
    printSpecificLevel_BT(root.rightCh, level - 1);
}

// Get the height of a binary tree.
public static int getHeight_BT (Node root) {
    if (root == null || (root.leftCh == null && root.rightCh == null)) return 0; // Base case.
    return 1 + Math.max (getHeight_BT(root.leftCh), getHeight_BT(root.rightCh));
}

// Print a binary tree level by level.
public static void printBT_LBL (Node root) {
    // Get the height of this binary tree.
    int height = getHeight_BT(root);
    for (int i = 0; i <= height; i ++) {
        printSpecificLevel_BT(root, i);
        System.out.println();
    }
}

Answer 1

printSpecificLevel_BT is O(n) since it looks at every node in the tree. However, with a simply change (returning when level == 0), you can make it O(min(n, 2^level)).

getHeight is O(n) since it looks at every node in the tree. printBT_LBL calls getHeight once and printSpecificLevel_BT height times, so its complexity is O(n + n*height) = O(n*height).

The space complexity of each is O(height) since it recurses all the way to the bottom of the tree. You can't say the O(log n) since the tree isn't necessarily balanced (unless it is).

Answer 2

For printSpecificLevel_BT() you have:

For printBT_LBL() you have: