MHB Is my AVL-tree height finding method correct?

[evinda]

Hello! (Wave)

I had a test today , it was given an AVL-tree and I had to find the height of the node with key $k$.

That's what I have tried:

Height(T,K){ 
  if (T==NULL) return; 
  pointer R; 
  R=LookUp(T,K); 
  int k=height(R); 
  return k; 
} height(pointer R){ 
  static j=0,l=0; 
  if (R==NULL) return 0; 
  if (R->lc!=NULL) l=1+height(R->lc); 
  if (R->rc!=NULL) j=l-height(R->lc)+height(R->rc); 
  if (R->rc==NULL and R->lc==NULL) return 1; 
  return max(l,j); 
}

Could you tell me if it is right? (Thinking)

 

[johng1]

Evinda,
Apparently, you are saying the height of an empty binary tree is 0. This is not the normal definition that the height of an empty binary tree is -1. So here's a simple height function:

int height(pointer R) {
  if (R==NULL) {
    return(-1);
  }
  return(1+max(height(R->LC),height(R->RC)));
}

So your height function is "correct" for your definition of height, but it's the worst implementation I can imagine.

Next, where is function LookUp? Presumably, the question wants you to write this function.

// assumes T is a value parameter
pointer LookUp(pointer T,int k) {
  while (T != NULL) {
     if (T->key == k) {
       return(T);
     }
     if (k < T->key) {
        T=T->LC;
     }
     else {
        T=T->RC;
     }
  }
  return(NULL);
}

If I were grading the question and was generous, I'd give you less than half credit.