Pathcopying

Pathcopying is a technique used in the implementation of persistent, immutable data structures to update a value without duplicating the entire structure. When a change is made, new nodes are created only along the path from the root to the modified location, while the remaining subtrees are shared between the old and new versions. This preserves immutability while enabling efficient updates.

In a tree or nested map, updating a key requires copying the nodes on the path from the root to the key; each new node points to the newly created child on the path, while any untouched child pointers reference the previously created subtrees. For example, inserting into a binary search tree may involve creating new nodes for the root and the nodes along the path to the inserted position; the old path remains intact for previous versions.

Complexity-wise, pathcopying typically costs time proportional to the length of the path being copied (often the tree depth, such as O(log n) for balanced trees) and uses space proportional to that path, due to the newly created nodes. The rest of the structure is shared, so overall memory growth per update is limited by the path length.

Applications of pathcopying are common in functional programming and libraries that provide persistent data structures, such as maps, sets, and trees, where immutability is a design goal. By combining pathcopying with structural sharing and copy-on-write semantics, these structures offer efficient, versioned access without full cloning. Limitations include overhead from node allocation and pointer indirection, and performance that depends on tree height and update frequency in mutable-heavy workloads.