Complexity of height of a Tree

Question

Consider the code :

int Tree::height(tree *node) {
    if (!node) return -1;

    return 1 + max(height(node->left), height(node->right));
}

What is the complexity of this method ? O(n) or O(log(n)) ?

I think it's O(n) , since in the worst case we'd check all the nodes , doesn't ?

Can you give an example of a better implementation ?

Thanks

Answer 1

I think you're checking all the nodes in all cases, not just the worst case. So yes, O(N).