Cycle Length Queries in a Tree

The implicit tree labels follow heap parenting: parent(x) = floor(x/2). Adding an edge between nodes a and b creates a cycle whose length is the existing tree distance between a and b plus one. Find that distance without constructing the tree: while a differs from b, divide the larger label by two and increment a counter. This moves each node toward their lowest common ancestor; when they meet, the counter is the tree path length, so return counter + 1 for the added edge. Starting the answer at one makes the extra edge explicit. Test equal nodes if the input allows them and ancestor-descendant pairs. Each query takes O(log(max(a,b))) time and O(1) space.