AVL tree

Question

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 ________.

Comments

S1:[213][657] = $^6C_3$ = $20$

S2:[213][675] = $^6C_3$ = $20$

S3:[231][657] = $^6C_3$ = $20$

S4:[231][675] = $^6C_3$ = $20$

Total possible orders = $80$

_________________________

These orders include some orders which leads to rotation due to imbalance e.g. 4,2,1. So it is required that we insert 6 after 2 & 2 after 6. Hence possible orders are $2*4!= 48$

---

Answer will be 48 . Solution is bogus

---

You should insert in the order {4, 2, 6, 1, 3, 5, 7} to make an AVL tree

Answer 1

total 48 sequences are possible

Comments

sorry it's my mistake !

---

@eyeamgj

then you have to find number of patterns will exist first ! ( there are 8 patterns )

then in each pattern you have to analyse how many ways you can insert it !

it's more complicated question !

---

Shaik Masthan MEANS WE HAVE TO CHECK ONE BY ONE ? NO ACTUAL CONCEPT TO KNOW THAT  WHY 2 IS  LEFT CHILD OF 3 NOT 1 ??

Answer 2

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

Comments

what if we insert in seq 4,2,6,3,5,1,7

after inserting till 4,2,6,3,5; i thing we have to balance node 2.

---

Nop. node 2 will have balance factor =1 after inserting 4,2,6,3,5

---

Thanks, I got it.

Answer 3

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.

Answer 4

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.