What is the maximum height of any AVL-tree with $7$ nodes? Assume that the height of a tree with a single node is $0$.
i think maximum number of node present in AVL tree in which root consider as height 0 is
Answer is B.
With $1$ node height is $0$.
Max height will come when each level contain min nodes.
Minimum Nodes in an AVL tree with height $n$ is $H(n) = H(n-1) + H(n-2) + 1$.
$H(0) = 1$.
$H(1) = 2$
$H(2) = H(1) + H(0) + 1 = 2+1+1 = 4$
$H(3) = H(2) + H(1) +1 = 4+2+1 = 7$.
So the max height with $7$ nodes is $3$.
I think H(n) represents an AVL tree with height n, having the minimum number of nodes.
because maximum no. of nodes an AVL tree with height n can have is 2n-1
you have written "Max Nodes in an AVL tree with height n is H(n) = H(n-1) + H(n-2) + 1." So I am saying change "Max nodes" to "minimum no. of nodes", because this recurrence is used to find the maximum height of an AVL tree with n nodes, not maximum no. of nodes with height h.
there are two formulae given on this page: http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Trees/AVL-height.html
So with these different answers, I don't get what should I infer. The proof of both these formulae looks good. But still they yield significantly different answers. Also the first one is more closet to the answer we get by using recurrence, while the second formula gives solution deviating a lot from the recurrence solution.
Gate_Keeda has written Minimum Nodes in an AVL tree with height n is H(n) = H(n-1) + H(n-2) + 1. right???
This makes the height as 3: