Cycle Length Queries in a Tree

hard tree lca bit manipulation

Problem

You are given an integer n describing a complete binary tree with 2^n − 1 nodes numbered from 1 to 2^n − 1. In this numbering, node v has a left child 2·v, a right child 2·v + 1, and a parent floor(v / 2).

For each query [a, b], imagine temporarily adding an extra edge between nodes a and b. That extra edge plus the existing tree path between a and b forms exactly one cycle. Return an array where each entry is the number of edges in that cycle. The added edge is then removed before the next query.

Inputn = 3, queries = [[5, 3], [4, 7], [2, 3]]

Output[4, 5, 3]

For [5, 3]: the path 5 → 2 → 1 → 3 has 3 edges, and the new edge closes the loop, giving a cycle of length 4.

def cycle_length_queries(n, queries):
    result = []
    for a, b in queries:
        steps = 1
        while a != b:
            if a > b:
                a //= 2
            else:
                b //= 2
            steps += 1
        result.append(steps)
    return result

function cycleLengthQueries(n, queries) {
  const result = [];
  for (const [a0, b0] of queries) {
    let a = a0, b = b0, steps = 1;
    while (a !== b) {
      if (a > b) a = Math.floor(a / 2);
      else b = Math.floor(b / 2);
      steps += 1;
    }
    result.push(steps);
  }
  return result;
}

class Solution {
    public int[] cycleLengthQueries(int n, int[][] queries) {
        int[] result = new int[queries.length];
        for (int q = 0; q < queries.length; q++) {
            int a = queries[q][0], b = queries[q][1], steps = 1;
            while (a != b) {
                if (a > b) a /= 2;
                else b /= 2;
                steps += 1;
            }
            result[q] = steps;
        }
        return result;
    }
}

vector<int> cycleLengthQueries(int n, vector<vector<int>>& queries) {
    vector<int> result;
    for (auto& q : queries) {
        int a = q[0], b = q[1], steps = 1;
        while (a != b) {
            if (a > b) a /= 2;
            else b /= 2;
            steps += 1;
        }
        result.push_back(steps);
    }
    return result;
}

Explanation

The big number n looks scary, but it is a red herring. We never build the tree — we only ever care about the two nodes named in a query, and the node ids alone encode the entire structure.

The key fact is the numbering rule: the parent of node v is v // 2 (integer division). So 5 → 2 → 1 and 3 → 1 just by repeated halving. The depth of a node is how many times you can halve it before reaching the root 1.

The cycle is the tree path from a to b closed off by the new edge, so its length equals (edges on the path) + 1. To count the path edges we walk both nodes up to their lowest common ancestor. The trick that keeps this simple: always move the larger of the two ids up by one level. A deeper node always has a larger id than its ancestors, so the bigger id is never shallower — halving it can only bring the two closer together, and they are guaranteed to meet at the LCA.

We count every halving step. When a == b we have reached the meeting point. The number of edges on the path is exactly the number of halvings performed, so the cycle length is that count plus one for the added edge. (Starting the counter at 1 and adding one per move folds the +1 in cleanly.)

Trace [5, 3]: ids 5 and 3. 5 > 3, so 5 → 2. Now 2 < 3, so 3 → 1. Now 2 > 1, so 2 → 1. Both are 1 — three moves, so the cycle length is 3 + 1 = 4.

Each query costs at most about n halvings (the tree height), and there is no extra data structure beyond the answer list.

Time: O(q · n) Space: O(1)