Sharing Unchanged Subtrees

Path copying shares unchanged subtrees between versions. If you update one leaf in a tree of $n$ nodes:

• Path length: $O(\log n)$ for balanced trees
• New nodes created: $O(\log n)$
• Shared nodes: $n - O(\log n)$

After $m$ updates:

• Total nodes: $O(n + m \log n)$
• Each version still has $n$ "logical" nodes

This is dramatically better than $O(nm)$ for full copies.

Here's the trick: immutability enables sharing. If a subtree never changes, all versions can point to the same physical subtree.