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)

  • $\begingroup$ 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? $\endgroup$
    – Nathaniel
    Commented Dec 2, 2022 at 15:12
  • $\begingroup$ yes, when the elements are inserted into the tree according to the sequence no rotation is needed $\endgroup$ Commented Dec 2, 2022 at 15:15
  • $\begingroup$ @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 $\endgroup$
    – Russel
    Commented Dec 2, 2022 at 15:39
  • $\begingroup$ @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 $\endgroup$ Commented Dec 3, 2022 at 11:40


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.