Update one node in a tree without cloning it

Editing one comment in a deep thread stored in React state cannot mutate the tree, but deep-cloning the whole thing throws away every memoisation you have. The answer is structural sharing: recreate only the nodes on the path from the root to the one that changed, and hand back every other subtree as the exact same object.

Implement updateNode(root, id, updater). root is a node shaped { id, ...otherProperties, children } where children is an array of nodes and may be missing. Find the node whose id equals id and replace it with the result of calling updater(node), which returns a new node object.

Return the new root. Every node on the path from the root down to the changed node must be a new object, not the original. Every subtree that does not contain the changed node must be returned as the identical object it already was, so next.children[1] === root.children[1] holds for an untouched sibling. When no node matches the id, return the original root itself, unchanged and by reference. Never modify the original tree.

What it has to do

• The returned tree contains the updated node.
• Every node on the path from the root to the changed node is a new object.
• Untouched subtrees are returned by reference, identical to the originals.
• When no node matches, the original root is returned by reference.
• The original tree is never mutated.

Your workspace