The problem is that you're doing the insertion iteratively. You need to either do it recursively with a BalanceTree call in each recursive call, or use some other form of trickyness like parent pointers, or an explicit stack.