Growing New Trees Without Copying the Old

When you propagate a succulent, you’re not photocopying the parent plant cell by cell. You take a leaf, it carries the blueprint, and it builds its own roots, its own structure. The two plants share a lineage but maintain separate physical forms. One grows left, the other leans toward the window—independent, but rooted in the same genetic memory.

In 1970s Lisp implementations, programmers faced a parallel problem: how do you “modify” data without mutating it? If every change requires copying an entire data structure, you drown in redundant allocations. The answer was structural sharing. When you create a modified version of a tree, you don’t duplicate the whole thing. You share the unchanged branches and only allocate new nodes along the path of change.

Here’s a binary tree in Go where inserting a value creates a new tree that shares structure with the original:

package main
import "fmt"

type Node struct { value int; left, right *Node }

func insert(n *Node, val int) *Node {
    if n == nil { return &Node{value: val} }
    if val < n.value { return &Node{n.value, insert(n.left, val), n.right} }
    return &Node{n.value, n.left, insert(n.right, val)}
}

func main() {
    t1 := insert(insert(nil, 5), 3)
    t2 := insert(t1, 7)
    fmt.Printf("Shared left branch: %p == %p is %v\n", t1.left, t2.left, t1.left == t2.left)
}

The same idea in Lua:

function insert(node, val)
    if not node then return {value = val} end
    if val < node.value then
        return {value = node.value, left = insert(node.left, val), right = node.right}
    else
        return {value = node.value, left = node.left, right = insert(node.right, val)}
    end
end

t1 = insert(insert(nil, 5), 3)
t2 = insert(t1, 7)
print("Shared:", t1.left == t2.left)

When you insert 7 into t1 to create t2, the left subtree isn’t copied—it’s shared. Both trees point to the same left branch in memory. The new tree inherited structure from its parent but grew independently to the right. Vegetative reproduction in data: the offspring carries the parent’s form but extends in its own direction.