boolean isBalanced(Tree *t,int *height)
{
if(t==NULL)
{
*height = 0;
return true;
}
int leftheight,rightheight;
boolean leftBalanced = isBalanced(t->lptr,&leftheight)
boolean rightBalanced = isBalanced(t->rptr,&rightheight)
bolean balanced = leftBalanced && rightBalanced && abs(leftheight-rightheight)<=1
*height = 1+max(leftheight,rightheight)
return balanced
}
I didn't dictate line by line but explained the above logic in words. I said the time complexity is O(n) where n is the no of nodes in the tree. But he insisted like idiot that the complexity is O(n^2) and was saying that for each subtree we will have to process all the nodes in the subtree but I kept saying that we process each node exactly once. I think he either didn't understand my answer properly or was stuck up with an inefficient algorithm he had in mind. My question is, is my algorithm correct or not?