1,131 views
1 votes
1 votes

Minimum number of internal nodes in an AVL tree with height 5?

Please give a standard procedure that can be applied to larger heights as well. I know the formula: S(h) = S(h-1) + S(h-2) + 1, but here it is asked for internal nodes only. Drawing a tree is tedious.

2 Answers

Best answer
0 votes
0 votes
i doubt whether i'm correct or not. please correct me if i'm wrong.

i tried drawing AVL trees with minimum nodes for height 2,3,4,5.

amd i observed that minimum no of internal nodes in an avl tree of height h I(h)=S(h-1)

minimum no of internal nodes in an avl tree of height 2 I(2)=S(1)=2

minimum no of internal nodes in an avl tree of height 3 I(3)=S(2)=4

minimum no of internal nodes in an avl tree of height 4 I(4)=S(3)=7

minimum no of internal nodes in an avl tree of height 5 I(5)=S(4)=12
selected by
0 votes
0 votes
well my answer is 11 minimum internal nodes (including root)  by just constructing tree.

Related questions

1 votes
1 votes
1 answer
1
kd..... asked Apr 13, 2019
756 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
2 votes
2 votes
3 answers
3
2 votes
2 votes
3 answers
4
learncp asked Jan 26, 2016
747 views
Insert the given values in the order in initially empty $\text{AVL}$ tree.$\text{34,21,10,27,24,43,15,6}$What is the value at the root of the tree$?$