Question

What order would I need to insert the numbers 1 to 7 into a new AVL tree in order to ensure that there was no need to perform a rotation.

Answer 1

There are total 12 such order are possible which result no rotation in AVL Tree

Order-1 : 5, 7, 3, 6,2,4, 1 // explained in the attached image

Order-2 : 5, 7, 3, 6,4,2, 1

Order-3: 5, 7, 3, 2,6,4, 1

Order-4: 5, 7, 3, 2,4,6, 1

Order-5: 5, 7, 3, 4,2,6, 1

Order-6: 5, 7, 3, 4,6,2, 1

Order-7 : 5, 3, 7, 6,2,4, 1

Order-8 : 5, 3, 7, 6,4,2, 1

Order-9: 5, 3, 7, 2,6,4, 1

Order-10: 5, 3, 7, 2,4,6, 1

Order-11: 5, 3, 7, 4,2,6, 1

Order-12: 5, 3, 7, 4,6,2, 1

Which Result No Rotation while inserting number into AVL Tree

Explanation:

AVL tree is Balance Binary search tree in which balance factor -1, 0, +1 are allow.

• balance factor =  height of left sub tree - height of Right sub tree
• balance factor =  | height of left sub tree - height of Right sub tree|

• balance factor =  if we consider mode then at every node balance factor should be 0 or 1
• balance factor =  difference should not be more than 1

Given Number between 1 to 7 means we need to use number 1,2,3,4,5,6,7 only