One - there is a terminating condition, I just didn't copy it, it didn't really matter as the recursion is not the cause of it...
Two, I have tried some print statements, but couldn't find the problem. I'll try the debugger...
Three, once again, I didn't copy the entire subroutine. I am using a check of $new to see if the node was shoved into the tree or not...

Thanks to you and anyone who replied, I'll try all your suggestions.