A binary search tree with the AVL property has no node whose left and right heights differ by more than 1. AVL trees maintain this property by maintaining balance information in their nodes, and rebalancing themselves when they find the property has been violated.

It is possible, however, to determine whether a tree without any balance information has the AVL property by a depth-first search of the tree, checking the property at every node and propagating the result upwards.

typedef struct {
unsigned int height;
unsigned int avl;
} avl_info;
avl_info binarytree_avl_recursive(const btnode *node)
{
avl_info info;
info.height = 0;
info.avl = 1;
unsigned int leftheight = 0, rightheight = 0;
if (node->left || node->right) {
unsigned int leftavl = 1, rightavl = 1;
avl_info child_info;
if (node->left) {
child_info = binarytree_avl_recursive(node->left);
leftheight = child_info.height + 1;
leftavl = child_info.avl;
}
if (node->right) {
child_info = binarytree_avl_recursive(node->right);
rightheight = child_info.height + 1;
rightavl = child_info.avl;
}
if (leftheight > rightheight) {
info.height = leftheight;
}
else {
info.height = rightheight;
}
info.avl = leftavl && rightavl && abs(leftheight - rightheight) <= 1;
}
return info;
}
unsigned int binarytree_avl(const binarytree *tree)
{
unsigned int result = 1;
if (tree->root != NULL) {
result = binarytree_avl_recursive(tree->root).avl;
}
return result;
}

## Related