Rerooting

Rerooting is a term used in multiple fields, most notably in graph theory and in horticulture. In graph theory and related algorithm design, rerooting refers to a dynamic programming technique for computing values for all possible roots of a tree. It relies on two passes: a bottom-up pass computes DP values with respect to an initial root; a top-down pass updates those values as the root shifts to neighboring nodes. The approach often uses associativity and commutativity of a combining operation, along with prefix and suffix accumulations to merge contributions from different branches efficiently.

Applications include calculating, for every node treated as root, quantities such as the sum of distances to all other nodes, counts of nodes in subtrees, or other aggregate statistics. The typical complexity is O(n) for a tree with n nodes, and the method can be adapted to various objective functions.

In biology and horticulture, rerooting is used informally to describe processes that establish or shift a plant’s root system. This can include rooting plant cuttings to create new root systems, or transplanting or grafting to align shoots with a new rootstock. In practice, successful rerooting depends on factors such as species-specific rooting ability, moisture, temperature, and hormonal signaling.