AVL Tree Height

Finding height is a $O(\log n)$ operation.

$$\text{minsize(h)}=\frac{{\varphi }^{h+2}-(1-\varphi {)}^{h+2}}{\sqrt{5}}-1$$

• With $\varphi$ as Golden Ratio
• With $h$ as the height of the sub tree

Code

int height(AVL_Node* node) {  
  if (node == NULL) return 0;  
  int left = height(node->left);  
  int right = height(node->right);  
  if (left > right) return left + 1;  
  return right + 1;  
}
 
void updateHeight(AVL_Node* node) { 
	node->height = height(node); 
}