Cycle Length Queries in a Tree

Hard

#2289Time: 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`.1 company

Data structures

Array Tree Binary Tree

Companies

Arcesium

Prompt

You are given an integer n. There is a complete binary tree with 2ⁿ - 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, 2^{n - 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] = [a_i, b_i]. For each query, solve the following problem:

Add an edge between the nodes with values a_i and b_i.
Find the length of the cycle in the graph.
Remove the added edge between nodes with values a_i and b_i.

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 i^th 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 <= 10⁵
queries[i].length == 2
1 <= a_i, b_i <= 2ⁿ - 1
a_i != b_i

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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).

Walkthrough

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:

Create a HashSet to store the ancestors of node a.
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.
Initialize a counter for the distance from b to the LCA, dist_b = 0.
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.
The first node found in the set is the LCA.
Now, calculate the distance from a to the LCA by traversing up from a and counting the steps until the LCA is reached.
The total path length is the sum of these two distances. The cycle length is this sum plus one.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int[] cycleLengthQueries(int n, int[][] queries) {6        int m = queries.length;7        int[] answer = new int[m];8 9        for (int i = 0; i < m; i++) {10            int u = queries[i][0];11            int v = queries[i][1];12 13            // Store ancestors of u in a set14            Set<Integer> ancestorsU = new HashSet<>();15            int curr = u;16            while (curr > 0) {17                ancestorsU.add(curr);18                curr /= 2;19            }20 21            // Find LCA and distance from v to LCA22            int distVToLCA = 0;23            curr = v;24            while (!ancestorsU.contains(curr)) {25                curr /= 2;26                distVToLCA++;27            }28            int lca = curr;29 30            // Find distance from u to LCA31            int distUToLCA = 0;32            curr = u;33            while (curr != lca) {34                curr /= 2;35                distUToLCA++;36            }37 38            answer[i] = distUToLCA + distVToLCA + 1;39        }40        return answer;41    }42}

Complexity

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`.

Trade-offs

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.

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.

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.

Walkthrough

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:

It first brings the deeper node up until it is at the same level as the other node.
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:

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

1class Solution {2    public int[] cycleLengthQueries(int n, int[][] queries) {3        int m = queries.length;4        int[] answer = new int[m];5 6        for (int i = 0; i < m; i++) {7            int u = queries[i][0];8            int v = queries[i][1];9            10            int pathLength = 0;11            while (u != v) {12                if (u > v) {13                    u /= 2;14                } else {15                    v /= 2;16                }17                pathLength++;18            }19            answer[i] = pathLength + 1;20        }21        return answer;22    }23}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int[] cycleLengthQueries(int n, int[][] queries) {4    int m = queries.length;5    int[] ans = new int[m];6    for (int i = 0; i < m; ++i) {7      int a = queries[i][0], b = queries[i][1];8      int t = 1;9      while (a != b) {10        if (a > b) {11          a >>= 1;12        } else {13          b >>= 1;14        }15        ++t;16      }17      ans[i] = t;18    }19    return ans;20  }21}

1class Solution {2public:3  vector<int> cycleLengthQueries(int n, vector<vector<int>> &queries) {4    vector<int> ans;5    for (auto &q : queries) {6      int a = q[0], b = q[1];7      int t = 1;8      while (a != b) {9        if (a > b) {10          a >>= 1;11        } else {12          b >>= 1;13        }14        ++t;15      }16      ans.emplace_back(t);17    }18    return ans;19  }20};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem