AVL Tree Rotation's

Question

Just a quick question about avl trees. If I had this tree:

    27
   /  \
  9    50
 / \
2   15
      \
       21

Why does it balance to this answer?:

    15
   /  \
  9    27
 /    /  \
2    21   50

Instead of this (or are they both valid?):

    21
   /  \
  15   27
 /  \    \
2    9    50

Answer 1

According to the retracing algorithm for AVL tree the balancing is done in two steps:

I. left rotation is done for the left sub-tree:

  |              |
  9              15
 / \            /  \
2   15   =>    9    21
     \        /
      21     2

II. right rotation is done for the whole tree:

      27           15
     /  \         /  \
    15   50 =>   9    27
   /  \         /    /  \
  9    21      2    21   50
 /
2

The second answer is simply incorrect as it didn't preserve order of elements.