= Undoing insertion of a new extreme key
If a key $q$ is smaller than every key of a finite <binary search tree> $R$, insert $q$ and then delete the minimum: the original tree, including its shape, is recovered. The insertion follows the leftmost search route and creates a new minimum leaf; deleting that leaf reverses the same route. The symmetric statement uses a fresh maximum. At a node with root $x$, the bounds on its children therefore let a direct <tree fold> reconstruct an untouched child from that child's insertion result. This gives a direct fold implementation of insertion without assuming that insertion is injective on arbitrary trees.
Back to article page
