Show the result of inserting 3 1 4 6 9 2 5 7 into an AVL tre

Show the result of inserting 3, 1, 4, 6, 9, 2, 5, 7 into an AVL tree. Make sure to show each rotation. Note: There are no double rotations in this sequence.

Solution

1.     (3)

2.    (3)
    /
(1)

3.    (3)
     / \\
   (1) (4)

   4.     (3)
    /   \\
       (1) (6)
         / \\
       (4) (9)

5.      (4)
      / \\
        (2) (6)
      / \\    / \\
   (1) (3) (5) (9)

6.        (4)
      / \\
        (2) (6)
    / \\    / \\
(1) (3) (5) (9)
                    \\
                    (7)