Euler-tour RMQ: answer static common ancestors in constant query time

Last updated: 4 Oct 20269 min read

tutorial

A rooted tree's Euler tour records a node on entry and after returning from each child. The first visit of each node gives an interval boundary; the shallowest tour entry between two first visits is their lowest common ancestor. This implementation stores the tour, depth at each tour position, first-visit positions, and a sparse table of minimum-depth tour indices. Two overlapping power-of-two table ranges cover any query interval, giving a constant-time minimum-index choice. The tree is unweighted; road distance follows from node depths and the selected ancestor. It rejects disconnected input and cycles, and assumes the rooted topology remains fixed after construction.

Operational case

The seven-depot road tree has a 13-entry Euler tour. Depots two and six first meet at depot one, and their path has four road edges. The tour repeats branch ancestors after each child returns, which is why it has 2N-1 entries rather than one entry per depot. Choosing the minimum node ID between first visits would be wrong; the sparse table compares depths. A query for the same depot returns that depot, and the distance is zero. Reorienting the root changes first visits and ancestors even if undirected path lengths remain the same, so the index must be rebuilt for a new root.

Working Python program

class DepotEulerAncestorIndex:
    def __init__(self, depot_count, roads, root=0):
        if depot_count < 1 or len(roads) != depot_count - 1 or not 0 <= root < depot_count:
            raise ValueError("expected a nonempty rooted tree")
        adjacent = [[] for _ in range(depot_count)]
        for first, second in roads:
            if not (0 <= first < depot_count and 0 <= second < depot_count) or first == second:
                raise ValueError("invalid tree edge")
            adjacent[first].append(second)
            adjacent[second].append(first)
        self.first = {}
        self.euler = []
        self.depth_at = []
        self.node_depth = {}

        def visit(node, parent, depth):
            if node in self.first:
                raise ValueError("cycle detected")
            self.first[node] = len(self.euler)
            self.node_depth[node] = depth
            self.euler.append(node)
            self.depth_at.append(depth)
            for child in adjacent[node]:
                if child == parent:
                    continue
                visit(child, node, depth + 1)
                self.euler.append(node)
                self.depth_at.append(depth)

        visit(root, -1, 0)
        if len(self.first) != depot_count:
            raise ValueError("disconnected depot network")
        self.sparse = [list(range(len(self.euler)))]
        span = 2
        while span <= len(self.euler):
            previous = self.sparse[-1]
            half = span // 2
            self.sparse.append([min(previous[start], previous[start + half],
                                    key=lambda index: (self.depth_at[index], index))
                                for start in range(len(self.euler) - span + 1)])
            span *= 2

    def lowest_common_depot(self, first_id, second_id):
        left, right = sorted((self.first[first_id], self.first[second_id]))
        power = (right - left + 1).bit_length() - 1
        width = 1 << power
        first_index = self.sparse[power][left]
        second_index = self.sparse[power][right - width + 1]
        best = min(first_index, second_index, key=lambda index: (self.depth_at[index], index))
        return self.euler[best]

    def road_distance(self, first_id, second_id):
        ancestor = self.lowest_common_depot(first_id, second_id)
        return self.node_depth[first_id] + self.node_depth[second_id] - 2 * self.node_depth[ancestor]


if __name__ == "__main__":
    network = DepotEulerAncestorIndex(7, [(0, 1), (1, 2), (1, 3), (3, 4), (3, 5), (5, 6)])
    print("common depot 2,6:", network.lowest_common_depot(2, 6))
    print("road distance 2,6:", network.road_distance(2, 6))
    print("Euler entries:", len(network.euler))

Output

common depot 2,6: 1
road distance 2,6: 4
Euler entries: 13

Time, space, and tradeoff

The DFS tour takes O(N) time and stores O(N) entries. Building the sparse table costs O(N log N) time and space; an LCA and unweighted road-distance query then take O(1) time and O(1) extra query memory. This Python DFS is recursive and can hit interpreter depth limits on a long chain even though the abstract preprocessing bound holds. Binary lifting uses comparable O(N log N) storage and O(log N) queries, while a balanced-parentheses encoding offers another static tree view. None of these static indexes handles link or cut operations without rebuilding or a different structure.

Common Mistakes

Do not confuse the minimum tour depth with the minimum depot ID.
Do not omit the return-to-parent entries from the Euler tour.
Do not reuse first-visit positions after changing the root or edges.
Do not claim this recursive Python build handles arbitrary-depth chains without a stack limit.

Connected lessons

Compare its update and query contract with FM-index backward search: narrow a suffix interval by character, Block-max postings: skip safe document-score regions, Piecewise interpolation indexes: predict a bounded rank window, then complete the structure audit and decision quiz.

data structures

range-query-structures