Answer: AVL trees

Question: Say we have the following binary search tree class.

class BinarySearchTree {
public:
    bool isAVL();
    int height(); // returns the subtree's height (a leaf has height 1)
private:
    int key;
    BinarySearchTree *left;
    BinarySearchTree *right;
};

Answer:

bool
BinarySearchTree::isAVL() {
    int left_height;
    int right_height;

    if(left) {
        left_height = left->height();
        if(!left->isAVL()) return false;
    } else {
        left_height = 0;
    }

    if(right) {
        right_height = right->height();
        if(!right->isAVL()) return false;
    } else {
        right_height = 0;
    }

    if(left_height > right_height + 1 || left_height < right_height - 1) {
        return false;
    } else {
        return true;
    }
}