I've been reading "purely functional data structures", and it's made me realize that there are quite a few data structures that are much easier to implement using mutable objects.

To implement a binary search tree, you have to return a new tree every time: Your new tree will have had to make a copy of each node that has been modified (the un-modified branches are shared). For your insert function this isn't too bad, but for me, things got fairly inefficient quickly when I started to work on delete and re-balance.

The other thing to realize is that you can go years writing object oriented code, and never really realize how terrible shared mutable state can be, if your code isn't run in a way that will expose concurrency problems.