Question: For each of the following, say whether the tree is an AVL tree. If not, say why not.
Answer:
4
/ \
2 8
/ \
0 10
\
11
This is not an AVL tree because the node with key 8 has a left subtree
of height 0 and right subtree of height 2. Because the two subtrees
have a height difference of 2, and the AVL property requires that the
height difference be at most 1, this is not an AVL tree.
4
/ \
2 8
/ / \
0 3 10
This is not an AVL tree because it is not a binary search tree: the
node with key 3 is in the right subtree of the node with key 4.
4
/ \
2 8
/ / \
0 7 10
\
11
This is an AVL tree.
4
/ \
2 8
/ /|\
0 3 9 10
This is not an AVL tree because it is not a binary search tree: the
node with key 8 has three children.