CODEWITHSUNDEEP
javabinary-treebig-otime-complexityspace-complexity
zproject89
zproject89

Reputation: 245

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

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();
    }
}

Upvotes: 1

Views: 2226

Answers (2)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

For printSpecificLevel_BT() you have:

enter image description here

For printBT_LBL() you have:

enter image description here

enter image description here

Upvotes: 1

Bernhard Barker
Bernhard Barker

Reputation: 55609

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).

Upvotes: 2

Related Questions