# Number of ways to insert elements into an AVL tree such that there are no rotations

How many ways can we insert elements { 1, 2, 3, .... 7 } to make an AVL tree so that it does not have any rotation?

I broke it down into 2 cases:

Case 1: height of tree = 2, (a complete binary tree) only 1 structure possible.

case 2: height of tree = 3, there will be 16 structures possible. there will not be an AVL tree of height 4 as AVL trees of height 4 require at least 12 nodes.

Now the problem is, I have the possible structures but I need to find the order of insertion into this structure(it is possible but I feel a better approach should be there)

• What do you mean by "the tree does not have any rotation"? Do you mean that no rotation is needed considering a given insertion order? Commented Dec 2, 2022 at 15:12
• yes, when the elements are inserted into the tree according to the sequence no rotation is needed Commented Dec 2, 2022 at 15:15
• @ArunMadhav, your title suggests that you are looking for the number of ways of inserting without rotation but in the content you are asking how to insert without rotation Commented Dec 2, 2022 at 15:39
• @Russel In my approach as I have the structures, I need to find the sequence of insertion for each structure but for 17 structures will be time-consuming, I want to know if there is a smart way to count the sequence of insertions into the structure or another approach to solve the problem Commented Dec 3, 2022 at 11:40