Redirected
recategorized by
8,757 views
7 votes
7 votes
The number of different orders are possible for elements 1, 2, 3, 4, 5, 6, 7 to be inserted in to empty AVL tree such that no rotation will be done and element ‘4’ is root are ________.
recategorized by

9 Answers

Best answer
30 votes
30 votes

total 48 sequences are possible

selected by
3 votes
3 votes

The tree is always like this:

   

Now, first you need to insert 4.

Then you need to insert 2 and 6 in 2 ways( first 2 and then 6 or first 6 and then 2).

Then remaining 4 elements(ie leafs) can be inserted in 4! ways.

Thus, total ways = 2 * 4! = 48

3 votes
3 votes

Elements ={1,2,3,4,5,6,7}

Root node is 4. // Root is at level '0' assume.

if 2 and 6 are present at level 1 then order of ${\color{Red} 1,{\color{Red} 3,{\color{Red} 5,{\color{Red} 7}}}}$ is not necessary

because it is balanced.This can be done in 4! ways.

And level 1 nodes ${\color{Red} 2,{\color{Red} 6}}$ also change in 2! ways.

Hence total no of orders=4!*2!=48.

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

Like one order is 4,${\color{Red} 2,{\color{Red} 6}}$,${\color{Green} 1,{\color{Green} 3,{\color{Green} 5,{\color{Green} 7}}}}$

Red color can be permuted and green color can be permuted no problem for AVL tree balanced factor.

I)4,2,6,1,3,5,7

II)4,2,6,3,1,5,7

....

These orders are not cause any problem for AVL property.

3 votes
3 votes

Final AVL Tree is shown in the above image.
Here root node as 4, possible sequence will be 4,(2,6),(1,3,5,7). So total no. of different possible orders are 2!*4!=2*24=48.

Related questions

3 votes
3 votes
1 answer
1
1 votes
1 votes
1 answer
2
kd..... asked Apr 13, 2019
759 views
here what to do first as FIZZA and IMRAN both are unbalanced than either to do RR rotation from FIZZA-IMRAN-NAVEEN or RL rotation from IMRAN-NAVEEN-LOVELY
1 votes
1 votes
1 answer
3
Rahul_Rathod_ asked Dec 28, 2018
1,043 views
what is the maximum possible hight of AVL tree with 54 node?is there any general method to solve this question?
1 votes
1 votes
1 answer
4
Lakshman Bhaiya asked Nov 6, 2018
672 views
The minimum number of node in an AVL Tree of height $10$ is ____________