Gate Question

Question

Consider the avl tree T in which left subtree contain quarter of the maximum number of nodes possible in the balanced AVL  tree of height  h and right sub tree consist of one fifth of the maximum number of nodes possible in AVL tree of height h. Assume that tree T may or may not be height balanced at parent.what is the total maximum possible number of nodes in T.

Comments

https://gateoverflow.in/85473/gate-question 

check this once.

---

though we can write an equation for the question. I dont think we can get a correct answer, as maximum nodes possible in BT are not divisible by 4,5. Hence I fell there is something fishy with this question

Answer 1

AVL tree is balanced binary search tree.

so maximum no of nodes at height 'h' is $2^{h+1}-1$

 Left subtree contains quarter of max no of nodes at height 'h' =$\frac{2^{h+1}-1}{4}$.

Right subtree contains on fifth of max nof nodes at height 'h' is=$\frac{2^{h+1}-1}{5}$.

Finally total no of nodes in AVL tree is=sum of nodes at left subtree+sum of nodes at right subtree+1.

=$\frac{2^{h+1}-1}{4}$.+$\frac{2^{h+1}-1}{5}$.+1

=.$\frac{9*2^{h+1}+11}{20}$