Q127: Height imbalance in AVL trees

Posted on by bytesoftheday

Question #127: AVL trees are an example of height balanced binary search trees where height difference between the left and the right child of any node is at most 1. Check out the tree below and decide which of its nodes have height imbalance.

AVL

Options:

  1. Node 5
  2. Nodes 5 and 8
  3. Nodes 5, 8 and 12
  4. Nodes 5, 8, 12 and 10

Solution: The correct option is second one.

For node 5, diff between the heights of left & right subtrees is |2-4| = 2 which is greater than 1.

For node 12, diiff between the heights of left & right subtrees is |2-1| = 1 which is well within the limits.

So we can see that only nodes 5 & 8 are unbalanced.