Data Structures and Algorithm Analysis in Java by Weiss Exer

Data Structures and Algorithm Analysis in Java by Weiss: Exercise 4.22

Design a linear-time algorithm that verifies that the height information in an AVL tree is correctly maintained and that the balance property is in order. (Only pseudo code is required).

Solution

  Make a boolean flag global, and assign it to true. Flag will decide the AVL property.

Call the function subHeightTree for root node.The function will return height of the subtree               rooted at that node.

Recursively call the function for left and right subtree.

Now check whether the difference between the two subtree\'s heights is <= 1.

If step-3 evaluates to be true, then do nothing.

Else, assign flag = false.

After the function returned for root, check the flag. If it\'s true, then Tree is balanced, else not.