On Finding Lowest Common Ancestors in Trees

Trees in an n-node forest are merged according to instructions in a given sequence, while other instructions in the sequence ask for the lowest common ancestor of pairs of nodes. We show that any sequence of $O(n)$ such instructions can be processed “on-line” in O(nlog n) steps on a random access computer. If we can accept our answer “off-line”, that is, no answers need to be produced until the entire sequence of instructions has been seen, then we may perform the task in O(nα (n)) steps, where α (n) is the very slowly growing inverse Ackermann function defined in [14]. A third algorithm solves a problem of intermediate complexity. We require the answers on-line, but we assume that all tree merging instructions precede the information requests. This algorithm requires O(n log log n) time. We apply the first on-line algorithm to a problem in code optimization, that of computing immediate dominators in a reducible flow graph. We show how this computation can be performed in O(nlog n) steps.