# Cycle Length Queries in a Tree
**Difficulty:** HARD
[External](https://leetcode.com/problems/cycle-length-queries-in-a-tree)
Canonical: https://scaleengineer.com/dsa/problems/cycle-length-queries-in-a-tree
**Data structures:** Array, Tree, Binary Tree
**Companies:** [Arcesium](https://scaleengineer.com/companies/arcesium)
---
## Problem
You are given an integer `n`. There is a **complete binary tree** with `2n - 1` nodes. The root of that tree is the node with the value `1`, and every node with a value `val` in the range `[1, 2n - 1 - 1]` has two children where:

* The left node has the value `2 * val`, and
* The right node has the value `2 * val + 1`.

You are also given a 2D integer array `queries` of length `m`, where `queries[i] = [ai, bi]`. For each query, solve the following problem:

1. Add an edge between the nodes with values `ai` and `bi`.
2. Find the length of the cycle in the graph.
3. Remove the added edge between nodes with values `ai` and `bi`.

**Note** that:

* A **cycle** is a path that starts and ends at the same node, and each edge in the path is visited only once.
* The length of a cycle is the number of edges visited in the cycle.
* There could be multiple edges between two nodes in the tree after adding the edge of the query.

Return _an array_ `answer` _of length_ `m` _where_ `answer[i]` _is the answer to the_ `ith` _query._

**Example 1:**

![](https://assets.glich.co/dsa/cycle-length-queries-in-a-tree/image0.png) 

**Input:** n = 3, queries = [[5,3],[4,7],[2,3]]
**Output:** [4,5,3]
**Explanation:** The diagrams above show the tree of 23 - 1 nodes. Nodes colored in red describe the nodes in the cycle after adding the edge.
- After adding the edge between nodes 3 and 5, the graph contains a cycle of nodes [5,2,1,3]. Thus answer to the first query is 4. We delete the added edge and process the next query.
- After adding the edge between nodes 4 and 7, the graph contains a cycle of nodes [4,2,1,3,7]. Thus answer to the second query is 5. We delete the added edge and process the next query.
- After adding the edge between nodes 2 and 3, the graph contains a cycle of nodes [2,1,3]. Thus answer to the third query is 3. We delete the added edge.

**Example 2:**

![](https://assets.glich.co/dsa/cycle-length-queries-in-a-tree/image1.png) 

**Input:** n = 2, queries = [[1,2]]
**Output:** [2]
**Explanation:** The diagram above shows the tree of 22 - 1 nodes. Nodes colored in red describe the nodes in the cycle after adding the edge.
- After adding the edge between nodes 1 and 2, the graph contains a cycle of nodes [2,1]. Thus answer for the first query is 2. We delete the added edge.

**Constraints:**

* `2 <= n <= 30`
* `m == queries.length`
* `1 <= m <= 105`
* `queries[i].length == 2`
* `1 <= ai, bi <= 2n - 1`
* `ai != bi`

# Approaches
## Path Traversal with Ancestor Set
This approach calculates the cycle length by first finding the Lowest Common Ancestor (LCA) of the two nodes in a query. The cycle length is the sum of the distances of each node to the LCA, plus one for the newly added edge. To find the LCA, we can trace the path from one node (`a`) to the root, storing all visited ancestors in a hash set. Then, we trace the path from the second node (`b`) to the root. The first node on this path that exists in our hash set is the LCA. After finding the LCA, we can calculate the distances and thus the cycle length.
**Time:** O(m * n), where `m` is the number of queries and `n` is the maximum depth of the tree. For each query, traversing up from both nodes takes O(log(node_value)) time, which is bounded by O(n). · **Space:** O(n) per query, where n is the maximum depth of the tree. This is for the `HashSet` which stores the ancestors of one node. The path to the root has a length of at most `n`.
**Pros:** The logic is straightforward and easy to follow, breaking the problem down into finding ancestors and then distances.
**Cons:** Requires extra space proportional to the depth of the tree (O(n)) for the hash set.; Involves multiple traversals: one to populate the set, one to find the LCA, and another to find the distance from the first node to the LCA.
### Explanation
In a tree, adding an edge between any two nodes `a` and `b` creates exactly one cycle. This cycle is composed of the path from `a` to `b` within the tree and the newly added edge `(a, b)`. Therefore, the length of the cycle is `distance(a, b) + 1`.

The path between `a` and `b` goes from `a` up to their Lowest Common Ancestor (LCA) and then down to `b`. The distance can be expressed as `distance(a, LCA) + distance(b, LCA)`.

The algorithm proceeds as follows for each query:
1.  Create a `HashSet` to store the ancestors of node `a`.
2.  Traverse from `a` up to the root (node 1) by repeatedly dividing by 2 (since `parent(x) = x / 2`). Add each node on this path to the set.
3.  Initialize a counter for the distance from `b` to the LCA, `dist_b = 0`.
4.  Traverse up from `b`. For each step, check if the current node is in the ancestor set of `a`. If not, move to the parent (`b = b / 2`) and increment `dist_b`.
5.  The first node found in the set is the `LCA`.
6.  Now, calculate the distance from `a` to the `LCA` by traversing up from `a` and counting the steps until the `LCA` is reached.
7.  The total path length is the sum of these two distances. The cycle length is this sum plus one.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] cycleLengthQueries(int n, int[][] queries) {
        int m = queries.length;
        int[] answer = new int[m];

        for (int i = 0; i < m; i++) {
            int u = queries[i][0];
            int v = queries[i][1];

            // Store ancestors of u in a set
            Set<Integer> ancestorsU = new HashSet<>();
            int curr = u;
            while (curr > 0) {
                ancestorsU.add(curr);
                curr /= 2;
            }

            // Find LCA and distance from v to LCA
            int distVToLCA = 0;
            curr = v;
            while (!ancestorsU.contains(curr)) {
                curr /= 2;
                distVToLCA++;
            }
            int lca = curr;

            // Find distance from u to LCA
            int distUToLCA = 0;
            curr = u;
            while (curr != lca) {
                curr /= 2;
                distUToLCA++;
            }

            answer[i] = distUToLCA + distVToLCA + 1;
        }
        return answer;
    }
}
```
### Algorithm
- For each query `[a, b]`, we need to find the length of the cycle formed by adding an edge between `a` and `b`.
- The cycle consists of the new edge `(a, b)` and the unique path between `a` and `b` in the tree.
- The length of the cycle is `1 + distance(a, b)`.
- The distance between `a` and `b` can be calculated as `distance(a, lca) + distance(b, lca)`, where `lca` is the Lowest Common Ancestor of `a` and `b`.
- This approach finds the `lca` by first storing all ancestors of node `a` (including `a` itself) in a hash set.
- Then, it traverses up from node `b` towards the root. The first node encountered that is already in the hash set is the `lca`.
- The distance from `b` to the `lca` is the number of steps taken in this upward traversal.
- The distance from `a` to the `lca` is calculated by another traversal up from `a` until the `lca` is reached.
- The total cycle length is `1 + distance(a, lca) + distance(b, lca)`.

## Iterative Path Unification
This is a highly efficient approach that finds the path length between two nodes `a` and `b` without any extra space. It relies on the specific properties of the complete binary tree's node numbering. The parent of any node `x` is `x/2`. This means a node with a larger value is generally deeper in the tree. By repeatedly moving the deeper node up, we can bring both nodes to the same level. Continuing this process, they will eventually meet at their LCA. The total number of upward moves is precisely the path length between them.
**Time:** O(m * n), where `m` is the number of queries and `n` is the maximum depth of the tree. Each query involves a loop that halves one of the numbers in each iteration. The number of iterations is bounded by O(log a + log b), which is O(n). · **Space:** O(1), as we only use a few variables to store the current node values and the path length. This does not count the output array.
**Pros:** Extremely space-efficient, using only O(1) extra space.; The code is very concise and fast, with a simple loop performing the core logic.; It's the optimal solution for this problem given the constraints.
**Cons:** The correctness of the simple `if (u > v)` logic might be less immediately obvious than the explicit LCA-finding method.
### Explanation
The core of the problem is to find the path distance between two nodes `a` and `b`. This can be done by simultaneously moving both nodes up towards the root until they meet. The total number of steps taken is the distance.

Instead of tracking levels explicitly, we can use a simpler, elegant trick. In the given tree structure, if two nodes are at different levels, the one at the deeper level will have a larger value. If they are at the same level, they are distinct. By always moving the node with the larger value up one level (i.e., `node = node / 2`), we ensure that we are always moving a node closer to the LCA.

This process effectively does two things:
1.  It first brings the deeper node up until it is at the same level as the other node.
2.  Once both nodes are at the same level, it continues to move them up one level at a time until they share a common parent, at which point the next move makes them equal (the LCA).

The algorithm is as follows:
1.  For each query `[a, b]`, initialize a `pathLength` counter to 0.
2.  Enter a loop that continues as long as `a` is not equal to `b`.
3.  Inside the loop, if `a > b`, update `a` to its parent: `a = a / 2`. Otherwise, update `b` to its parent: `b = b / 2`.
4.  Increment `pathLength` in each iteration.
5.  When the loop terminates, `pathLength` will hold the distance between the original `a` and `b`.
6.  The answer for the query is `pathLength + 1`.

```java
class Solution {
    public int[] cycleLengthQueries(int n, int[][] queries) {
        int m = queries.length;
        int[] answer = new int[m];

        for (int i = 0; i < m; i++) {
            int u = queries[i][0];
            int v = queries[i][1];
            
            int pathLength = 0;
            while (u != v) {
                if (u > v) {
                    u /= 2;
                } else {
                    v /= 2;
                }
                pathLength++;
            }
            answer[i] = pathLength + 1;
        }
        return answer;
    }
}
```
### Algorithm
- The cycle length is `1 + distance(a, b)`.
- The distance between `a` and `b` is the number of edges on the unique path connecting them.
- This path can be found by moving from `a` and `b` upwards towards the root until they meet at their LCA.
- A key observation in this tree structure is that a node with a larger value is always deeper than or at the same level as a node with a smaller value.
- The algorithm leverages this: in a loop, it compares `a` and `b` and moves the one with the larger value up to its parent (`node = node / 2`).
- A counter is incremented for each move.
- The loop continues until `a` and `b` become equal. At this point, they have met at their LCA.
- The value of the counter is the total path length between the original `a` and `b`.
- The cycle length is `counter + 1`.

# Solutions
### Java

```java
class Solution {
public
  int[] cycleLengthQueries(int n, int[][] queries) {
    int m = queries.length;
    int[] ans = new int[m];
    for (int i = 0; i < m; ++i) {
      int a = queries[i][0], b = queries[i][1];
      int t = 1;
      while (a != b) {
        if (a > b) {
          a >>= 1;
        } else {
          b >>= 1;
        }
        ++t;
      }
      ans[i] = t;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> cycleLengthQueries(int n, vector<vector<int>> &queries) {
    vector<int> ans;
    for (auto &q : queries) {
      int a = q[0], b = q[1];
      int t = 1;
      while (a != b) {
        if (a > b) {
          a >>= 1;
        } else {
          b >>= 1;
        }
        ++t;
      }
      ans.emplace_back(t);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]: ans = [] for a, b in queries: t = 1 while a != b: if a > b: a >>= 1 else: b >>= 1 t += 1 ans . append(t) return ans

```