Since your array is sorted from smallest to largest, when you try to insert the, say, 15000th node using insertPrep
(see the loop in tree()
), you are going to recursively call insert(AvlNode node, AvlNode newNode)
15000 times.
This is due to the test in insert
if (node.key > newNode.key){
if(node.left!=null){node.left=insert(node.left , newNode);}
else{node.left=newNode;}
}
The recursions are too deep
Recursion is probably not your best choice to find the location in the tree and you should resort to a loop which will be more efficient anyway because you do not have to accumulate the frames between the calls.
Alternatively, use a language such as Scala that knows about tail recursion and automatically unfolds tail recursions to loops at compile time.
EDIT The explanation for the Overflow is probably over simplistic. See comments below