Assuming that all keys in an AVL tree are distinct positive integers. Suppose that the root node of an AVL tree T holds the key N. What can be estimated largest possible number of nodes in T ?
We know that AVL tree follow following properties :
Self balancing Binary Search Tree.
The heights of the two child subtrees of any node differ by at most one;
If at any time they differ by more than one, rebalancing is done to restore this property.
I know that minimum number of nodes in AVL tree is given by this recursion :
S(h) = S(h-1) + S(h-2) + 1.
As you mentioned for different positive integers,so I am assuming numbers will be 1 to N,for some positive integer N>=2:: Answer is::
N-1+2^{[log(N-1)]+2} ,
where in above formula,
N=ROOT KEY
log x= logarithmic value of x to base 2
[ x]=Floor of x i.e. highest integer less than or equal to x and
x^y= x raise to power of y.
Explanation:: As AVL Tree with root N will contain exactly N-1 nodes in it's left subtree with height log(N-1) and it's left subtree will be balanced in itself with height balance property of AVL Tree.
Let us say the height of left subtree be h ::
So , it's right subtree can be of h+1height and hence can contain at max -1+ 2^{h+1+1} nodes,
hence the answer will be left subtree nodes +1+right subtree nodes. Now left subtree nodes=N-1,so
MAXIMUM NO. OF NODES IN AVL TREE WITH ROOT NODE N WILL BE::
N-1+2^{[log(N-1)]+2}.
NOTE :: Above formula is valid only for N>=2 BUT FOR N=1, no. Of nodes will be 2.