Describe an efficient algorithm for computing the height of a given AVL tree. Yo

Question

Describe an efficient algorithm for computing the height of a given AVL tree. Your algorithm should run in time O(log n) on an AVL tree of size n. In the pseudocode, use the following terminology: T.left, T.right, and T.parent indicate the left child, right child, and parent of a node T and T.balance indicates its balance factor (-1, 0, or 1). For example if T is the root we have T.parent=nil and if T is a leaf we have T.left and T.right equal to nil. The input is the root of the AVL tree. Justify correctness of the algorithm and provide a brief justification of the runtime

no handwriting please

Explanation / Answer

Assumption- AVL tree is balanced

int max(int a, int b)

{

return a>b?a:b;

}

In Height(node * T, int &h)

{

if(T==NULL) return -1;

int l,r;

*h = max(height(T->left,&l),height(T->right,&r))+1

return *h;

}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.