Skip to main content
Talentd

Cycle Length Queries in a Tree - Solution & Explanation

HardArrayTreeBinary Tree13 min readAsked at: Arcesium
Practice this problem

Problem Statement

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:

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

Approach Overview

Problem Overview: You are given queries on an infinite complete binary tree where node i has parent i/2. For each query [a, b], an extra edge is temporarily added between the two nodes. That edge forms exactly one cycle. The task is to compute the length of that cycle for every query.

Approach 1: Using an Array (Path to Root Comparison) (Time: O(log n) per query, Space: O(log n))

This approach builds the path from each node to the root and stores those ancestors in arrays. Starting from a and b, repeatedly divide by 2 to move up the tree until reaching the root. Once both ancestor paths are built, scan from the root side to locate the lowest common ancestor (LCA). The distance from a to the LCA plus the distance from b to the LCA gives the number of tree edges between the nodes. Adding the new edge forms a cycle, so the final cycle length becomes distance + 1. Each node moves up at most log₂(n) levels because the structure behaves like a heap-style binary tree. This method is straightforward and easy to reason about since the ancestor lists make the LCA detection explicit.

Approach 2: Using a Linked List / Pointer Walk (Upward Traversal) (Time: O(log n) per query, Space: O(1))

This approach avoids storing ancestor paths. Instead, simulate climbing toward the root from both nodes simultaneously. While a != b, always move the larger node upward by replacing it with a/2 or b/2. Because node labels increase as you go down the tree, the larger label must be deeper. Each upward step reduces the depth difference until both pointers meet at their LCA. Count the number of steps taken during this process. The cycle length equals the step count plus one for the added edge. The method relies on the heap-like numbering of this tree structure and performs only simple integer operations. No auxiliary data structures are needed beyond a counter.

The key observation: the cycle formed after adding the edge equals distance(a, b) + 1. Computing the distance in this implicit tree reduces to repeatedly moving nodes toward their lowest common ancestor. Because the height of the tree grows logarithmically, each query runs in O(log n) time.

Recommended for interviews: The upward traversal method is the expected solution. It demonstrates understanding of implicit tree structures and LCA reasoning without building the tree explicitly. The array-based approach still shows solid reasoning about ancestor paths, but the pointer-walk solution is cleaner and uses constant space. Both rely on properties of a heap-indexed array-like representation of a binary tree.

Approach 1: Approach 1: Using an Array

This approach focuses on solving the problem using a simple array. We iterate through the array to achieve the desired result based on the problem requirements.

The given code iterates over the array, printing each element.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Approach 2: Using a Linked List

This approach utilizes a linked list to manage elements dynamically. We traverse the linked list and perform operations analogous to those required in a more static array setting.

Here, C is used to implement a simple singly linked list, where the nodes are traversed to print each element's data.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n) for linked list nodes

Try this approach in the editor →

Approach 3: Finding the Lowest Common Ancestor

For each query, we find the lowest common ancestor of the two nodes a and b, and record the number of steps taken upwards. The answer to the query is the number of steps plus one.

To find the lowest common ancestor, if a > b, we move a to its parent node; if a < b, we move b to its parent node. We accumulate the number of steps until a = b.

The time complexity is O(n times m), where m is the length of the queries array.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Using an Array

Time Complexity: O(n)
Space Complexity: O(1)

Approach 2: Using a Linked List

Time Complexity: O(n)
Space Complexity: O(n) for linked list nodes

Finding the Lowest Common Ancestor—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Array (Store Path to Root)O(log n) per queryO(log n)Useful when you want explicit ancestor paths and clearer LCA reasoning
Linked List / Pointer Upward TraversalO(log n) per queryO(1)Preferred solution for interviews due to constant space and simple implementation

Video Solution

Weekly Contest 324 | Cycle Length Queries in a Tree • codingMohan • 764 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Cycle Length Queries in a Tree easy or hard?
The problem is labeled Hard because it requires recognizing the implicit tree structure and reducing the task to a lowest common ancestor distance problem. Once that insight is clear, the implementation becomes short and efficient with O(log n) time per query.
Cycle Length Queries in a Tree Python/Java solution
Python and Java implementations typically use a loop that moves the larger node upward until both nodes become equal. Each iteration divides the deeper node by two and increments a counter. After the loop finishes, add one to the counter to represent the extra edge that creates the cycle.
How to solve Cycle Length Queries in a Tree in O(n)?
The typical optimized solution processes each query independently in O(log n) time using upward traversal toward the LCA. During each step, divide the larger node by 2 until both nodes match. Count the steps and add one to represent the newly added edge forming the cycle. For q queries, the full runtime is O(q log n).
What is the best approach for Cycle Length Queries in a Tree?
The most efficient approach is upward traversal to the lowest common ancestor (LCA). For each query, repeatedly move the larger node upward by dividing it by 2 until both nodes meet. The number of steps taken gives the distance between nodes, and the cycle length is distance + 1. This runs in O(log n) time per query and O(1) space.
Is Cycle Length Queries in a Tree asked at Google/Amazon/Meta?
This type of problem reflects common interview themes such as lowest common ancestor, binary tree traversal, and heap-style indexing. Variations of LCA and implicit tree navigation frequently appear in interviews at companies like Google, Amazon, and Meta. The problem tests reasoning about tree structure without explicitly building the tree.
What data structure is used in Cycle Length Queries in a Tree?
The problem relies on properties of a complete binary tree where node indices behave like a heap stored in an array. The optimal approach does not require building an explicit tree structure. Instead, simple integer operations simulate moving to a parent node using division by two.
What is the time complexity of Cycle Length Queries in a Tree?
Each query requires moving nodes up the binary tree toward their lowest common ancestor. Since the height of a complete binary tree is about log2(n), the traversal takes O(log n) time. With q queries, the total complexity becomes O(q log n). Space complexity can be O(1) with the pointer traversal approach.

Ready to solve this problem?

Practice Cycle Length Queries in a Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Lowest Common Ancestor of a Binary Tree

Next

Path In Zigzag Labelled Binary Tree