2509. Cycle Length Queries in a Tree LeetCode Solution

Last updated: March 5, 2025

In this guide, you will get 2509. Cycle Length Queries in a Tree LeetCode Solution with the best time and space complexity. The solution to Cycle Length Queries in a Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Cycle Length Queries in a Tree solution in C++
Cycle Length Queries in a Tree solution in Java
Cycle Length Queries in a Tree solution in Python
Additional Resources

2509. Cycle Length Queries in a Tree LeetCode Solution image

Problem Statement of Cycle Length Queries in a Tree

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:

Add an edge between the nodes with values ai and bi.
Find the length of the cycle in the graph.
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:

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:

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

Complexity Analysis

Time Complexity: O(q\log n)
Space Complexity: O(q)

2509. Cycle Length Queries in a Tree LeetCode Solution in C++

class Solution {
 public:
  vector<int> cycleLengthQueries(int n, vector<vector<int>>& queries) {
    vector<int> ans;

    for (const vector<int>& query : queries) {
      ans.push_back(1);
      int a = query[0];
      int b = query[1];
      while (a != b) {
        if (a > b)
          a /= 2;
        else
          b /= 2;
        ++ans.back();
      }
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

2509. Cycle Length Queries in a Tree LeetCode Solution in Java

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

    for (int i = 0; i < queries.length; ++i) {
      ++ans[i];
      int a = queries[i][0];
      int b = queries[i][1];
      while (a != b) {
        if (a > b)
          a /= 2;
        else
          b /= 2;
        ++ans[i];
      }
    }

    return ans;
  }
}
// code provided by PROGIEZ

2509. Cycle Length Queries in a Tree LeetCode Solution in Python

class Solution:
  def cycleLengthQueries(self, n: int, queries: list[list[int]]) -> list[int]:
    def getCycleLength(a: int, b: int):
      cycleLength = 1
      while a != b:
        if a > b:
          a //= 2
        else:
          b //= 2
        cycleLength += 1
      return cycleLength

    return [getCycleLength(*query) for query in queries]
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents