MadeEasy Test Series: Programming & DS - Binary Tree

Question

The number of ways we can insert elements { 1, 2, 3, .... 7 } to make an AVL tree, so that it does not have any rotation are _______ ?

Comments

it will be 96+96+48=240

right?

really calculative one

---

Someone Please clarify what is wrong i am thinking here.

suppose 3 is the root,in this case {12} can be on left sub tree and {4567} can be on right sub tree,considering to form a AVL which is a BBST number of BST on Left is 2 and number of BST on right subtree is 14 using catalan number but here we need to subtract 2(when 4567 is in a skew i.e two ways 3->4->5->6->7 and 3->7->6->5->4 ) from 14 because these the only case which can violate property of AVL i.e height atmost 1.

so number of AVL tree is 2*12=24 with 3 as root.

---

https://gateoverflow.in/243285/avl-tree?show=243306

Answer 1

with 3 as root we can insert in 8 different combinations of avls as {3} {2,6}{1,5,7}{4} ;

{3}{1,6}{2,5,7}{4};

{3}{2,5}{1,4,6}{7} ;

{3}{1,5}{2,4,6}{7};

{3}{2,6}{1,4,7}{5};

{3}{1,6}{2,4,7}{5};

{3}{2,5}{1,4,7}{6};

{3}{1,5}{2,4,7}{6};

where each of the combination permute in 2!*3! =12 ways

this gives total of 12*8 i.e. 96 insertion sequences with 3 as root

with 4 as root, balanced avl only kind of AVL is created and sequences is {4}{2,6}{1,3,5,7} which gives 48 permutations

with 5 as root we have 8 insertion sequence with 12 permutations in each {same as 3 as root} i.e. total of 12*8 i.e 96 sequence.

So total ways to insert keys in AVL without rotation is 48+2*96 i.e 48+ 192 i.e. 240..................

Comments

....with 4 as root made easy solution gives there are 80 ways and your solution gives 48.

---

@roman_1997 why  4-2-1 or 4-2-3 will not cause imbalance , I think it will cause LEFT-LEFT imbalance and LEFT -RIGHT imbalance respectively?

---

@roman_1997 48 is the correct for 4 as root element. 80 is given answer as you posted, Made easy has given wrong solution.

Answer 2

with 3 as root we are able to create 8 trees which are balanced BST. With 4 as root we can create just one balanced BST and with 5 as root we can create again 8 BST. Hence 17 BST should be the answer

Comments

There are 17 trees possible. But question is asking ways to insert elements into these trees , so that there is no rotation  & there are multiple order in which we can insert elements into these trees.

---

CAN U PLZ GIVE ONE ORDER WITH 3 AS ROOT WHICH DONT NEED ANY ROTATION

---

(3) ( 2, 6 ) (1,5,7) (4)​  - elements with in  ( ) can be permuted.  

- this gives 12 orders

- each order giving same tree.

- 1 out of Rohit's 8 trees.

---

- Each 16 tree can be permuted like  this giving 12 orders each (each distinct).

- 16 tree * 12 order each giving  192 sequences.

---

​48 sequences  for ur one Complete Binary AVL tree(As given in above answer).

So, I got - 48 + 192 = 240.

Answer 3

THERE WILL BE ONLY 2!4! WAYS TO DO THIS

REASON- You should insert in the order 4; 2; 6; 1; 3; 5; 7 to make an AVL tree.
The ordering of 2; 6and the ordering of 1; 3; 5; 7 do not matter. One can see the
resulting binary search tree is perfectly balance therefore an AVL tree

Comments

Why 3 can't be the root? Whats the problem with order.. 3,2,5,1,4,6,7  ?

Answer 4

48 POSSIBILITIES. THE ORDER SHOULD BE(4261357) AND U CAN INTERCHANGE (2,6) AND (1357) IN BETWEEN THEM (2,6) CAN BE ARRANGED IN 2 WAYS AND (1,3,5,7)IN 24 WAYS THIS LEADS TO A TOTAL OF 48(2*24) WAYS