Yes, behind the scenes every one of those statements will make a shallow copy of the object. But it isn't just that object necessarily. For example, if you modify a tree node, then not only does that node needs cloning, its parent does too (since the modified parent needs to point to the new node), and so on until the root, which results in h = O(log(n)) new objects to create an entirely new tree. (h is the height of the tree).

What you get out if it is (a) safety, (b) understandability, which are wonderful properties to have as long as the end result is performing adequately. Implementing concurrent tree or graph traversals under conventional mutation is painful; the Java collection libraries simply throw a ConcurrentModificationException. The equivalent code for readonly traversals of immutable data structures is simplicity itself. You also get versioning and undo's for free.