I think you're checking all the nodes in all cases, not just the worst case. So yes, O(N).
Complexity of height of a Tree
-
13-07-2023 - |
Pregunta
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
Solución
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow