LeetCode 2509 - Cycle Length Queries in a Tree

LeetCode Problem 2509

Difficulty: 🔴 Hard
Topics: Array, Tree, Binary Tree

Solution

Problem Understanding

The problem gives us a complete binary tree where nodes are labeled in the same way as a binary heap.

For every node with value x:

• Its left child is 2 * x
• Its right child is 2 * x + 1

The tree contains all node values from 1 to 2^n - 1.

For each query [a, b], we temporarily add an extra edge directly connecting node a and node b. Since the original structure is a tree, there is exactly one simple path between any two nodes. Adding one additional edge between a and b creates exactly one cycle.

The length of that cycle equals:

• the number of edges in the original path between a and b
• plus the newly added edge

So the real task is to compute the distance between nodes a and b in the binary tree, then add 1.

The output for each query is therefore:

distance(a, b) + 1

The constraints are important:

• n <= 30
• m <= 10^5

Even though the tree can theoretically contain up to 2^30 - 1 nodes, we are never asked to explicitly build it. Constructing the entire tree would be impossible in memory.

The node numbering scheme gives us a very important property:

• The parent of node x is x // 2

This means we can move upward toward the root efficiently without storing the tree.

Some important edge cases include:

• One node being the ancestor of the other
• Queries involving the root node
• Deep nodes near 2^30 - 1
• Large numbers of queries where inefficient traversal would time out

The problem guarantees:

• a != b
• All node values are valid
• The graph is always a tree before adding the extra edge

These guarantees simplify the implementation because we never need to handle invalid input or disconnected structures.

Approaches

Brute Force Approach

A straightforward solution would explicitly model the binary tree as a graph.

For each query:

1. Build or traverse the tree
2. Use BFS or DFS to find the shortest path between a and b
3. Add 1 to account for the newly added edge

This works because a tree has exactly one simple path between any two nodes.

However, this approach is far too slow and memory intensive. The tree can contain up to:

2^30 - 1 ≈ 1 billion nodes

Building such a graph is impossible.

Even if we avoided full construction and searched dynamically, performing graph traversals for up to 10^5 queries would still be inefficient.

Key Insight

The node numbering directly encodes the tree structure.

For any node:

parent(x) = x // 2

This means we can move upward from any node toward the root without storing the tree.

The path between two nodes can be found by repeatedly moving the deeper node upward until both nodes become equal. This is exactly the process of finding the Lowest Common Ancestor using parent jumps.

Every upward move corresponds to one edge in the path.

Therefore:

• Count how many upward moves are needed until the two nodes meet
• Add 1 for the newly inserted edge

Because node values are at most 2^30 - 1, each node has height at most 30. So every query requires at most about 60 upward moves.

This is extremely efficient.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m * 2^n)	O(2^n)	Explicit traversal or graph construction is infeasible
Optimal	O(m * log N)	O(1)	Uses parent relationships directly from node values

Here, N = 2^n - 1.

Algorithm Walkthrough

1. Initialize an empty answer list.
2. For each query [a, b], start a counter at 1.

The counter starts at 1 because the newly added edge between a and b is always part of the cycle. 3. While a and b are different, move the larger node upward.

Since larger node values are always deeper or at the same depth in this numbering scheme, moving the larger value upward helps both nodes converge toward their Lowest Common Ancestor. 4. If a > b, replace a with a // 2.

This moves node a to its parent. 5. Otherwise, replace b with b // 2.

This moves node b to its parent. 6. Increment the counter after every upward move.

Each move represents traversing one tree edge in the original path between a and b. 7. Continue until a == b.

At this point, both nodes have met at their Lowest Common Ancestor. 8. Append the counter to the answer list. 9. Return the answer list after processing all queries.

Why it works

A tree contains exactly one simple path between any two nodes. Repeatedly moving the deeper node upward reconstructs this path edge by edge until both nodes meet at their Lowest Common Ancestor.

The number of upward moves equals the distance between the two nodes in the original tree. Since the added edge also belongs to the cycle, the final cycle length is:

distance(a, b) + 1

The algorithm counts exactly these edges, so it always produces the correct answer.

Python Solution

from typing import List

class Solution:
    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        answers = []

        for a, b in queries:
            cycle_length = 1

            while a != b:
                if a > b:
                    a //= 2
                else:
                    b //= 2

                cycle_length += 1

            answers.append(cycle_length)

        return answers

The implementation follows the algorithm directly.

The answers list stores the result for every query.

For each query, the variable cycle_length starts at 1 because the extra edge added between the two nodes is always included in the cycle.

The while a != b loop continues until both nodes meet at their Lowest Common Ancestor.

Inside the loop:

• The larger node is moved upward using integer division by 2
• The cycle length counter increases by 1

Each iteration corresponds to traversing one edge in the tree.

Once both nodes become equal, the entire path between them has been counted, and the final cycle length is appended to the result list.

The parameter n is not explicitly used because the node labels already contain all structural information needed to navigate the tree.

Go Solution

func cycleLengthQueries(n int, queries [][]int) []int {
    answers := make([]int, 0, len(queries))

    for _, query := range queries {
        a := query[0]
        b := query[1]

        cycleLength := 1

        for a != b {
            if a > b {
                a /= 2
            } else {
                b /= 2
            }

            cycleLength++
        }

        answers = append(answers, cycleLength)
    }

    return answers
}

The Go implementation mirrors the Python solution closely.

A slice named answers is preallocated with capacity equal to the number of queries for better efficiency.

Go uses integer division automatically for integers, so a /= 2 correctly moves a node to its parent.

No special handling for overflow is needed because the maximum node value is below 2^30, which easily fits inside Go's standard int type on LeetCode platforms.

Worked Examples

Example 1

Input:

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

Query 1: [5, 3]

We trace the algorithm step by step.

Step	a	b	Action	cycle_length
Initial	5	3	Start	1
1	2	3	5 -> 2	2
2	2	1	3 -> 1	3
3	1	1	2 -> 1	4

Nodes meet at 1.

Result:

4

The cycle is:

5 -> 2 -> 1 -> 3 -> 5

Query 2: [4, 7]

Step	a	b	Action	cycle_length
Initial	4	7	Start	1
1	4	3	7 -> 3	2
2	2	3	4 -> 2	3
3	2	1	3 -> 1	4
4	1	1	2 -> 1	5

Result:

5

Query 3: [2, 3]

Step	a	b	Action	cycle_length
Initial	2	3	Start	1
1	2	1	3 -> 1	2
2	1	1	2 -> 1	3

Result:

3

Final output:

[4, 5, 3]

Example 2

Input:

n = 2
queries = [[1,2]]

Query: [1, 2]

Step	a	b	Action	cycle_length
Initial	1	2	Start	1
1	1	1	2 -> 1	2

Result:

2

The cycle is:

1 -> 2 -> 1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m * log N)	Each query moves upward through tree height
Space	O(1)	Only a few variables are used

The height of the binary tree is at most n, and n <= 30.

For every query, each upward move divides a node value by 2, so the number of iterations is bounded by the tree height.

Therefore, each query takes at most O(log N) time, where N is the maximum node value.

Since there are m queries, the total complexity is:

O(m * log N)

The algorithm uses constant extra memory because it stores only a few integers while processing each query.

Test Cases

from typing import List

class Solution:
    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        answers = []

        for a, b in queries:
            cycle_length = 1

            while a != b:
                if a > b:
                    a //= 2
                else:
                    b //= 2

                cycle_length += 1

            answers.append(cycle_length)

        return answers

solution = Solution()

# Provided example 1
assert solution.cycleLengthQueries(3, [[5, 3], [4, 7], [2, 3]]) == [4, 5, 3]

# Provided example 2
assert solution.cycleLengthQueries(2, [[1, 2]]) == [2]

# Nodes with same parent
assert solution.cycleLengthQueries(4, [[4, 5]]) == [3]

# One node is ancestor of another
assert solution.cycleLengthQueries(5, [[2, 8]]) == [3]

# Root involved
assert solution.cycleLengthQueries(5, [[1, 31]]) == [6]

# Deep nodes on opposite sides
assert solution.cycleLengthQueries(5, [[16, 31]]) == [9]

# Multiple mixed queries
assert solution.cycleLengthQueries(
    6,
    [[10, 11], [14, 15], [8, 13]]
) == [3, 3, 6]

# Large node values near limit
assert solution.cycleLengthQueries(
    30,
    [[1073741823, 1073741822]]
) == [3]

# Different subtree depths
assert solution.cycleLengthQueries(
    6,
    [[9, 28]]
) == [8]

print("All tests passed!")

Test Summary

Test	Why
[[5,3],[4,7],[2,3]]	Validates official example
[[1,2]]	Smallest meaningful tree
[[4,5]]	Tests sibling nodes
[[2,8]]	Tests ancestor-descendant relationship
[[1,31]]	Tests root participation
[[16,31]]	Tests distant nodes
Mixed multiple queries	Ensures repeated processing works correctly
Very large node values	Verifies logarithmic behavior
Uneven subtree depths	Tests repeated upward traversal

Edge Cases

One Node Is an Ancestor of the Other

A common source of bugs is when one node lies directly on the path to the root of the other node.

For example:

a = 2
b = 8

The path is:

8 -> 4 -> 2

The implementation handles this naturally because the deeper node repeatedly moves upward until both values match. No special ancestor detection is needed.

Queries Involving the Root

The root node has no parent, so algorithms that assume every node can continue moving upward may fail.

For example:

a = 1
b = 31

The implementation stops immediately once both nodes become equal, so the root is handled safely without invalid parent access.

Very Large Node Values

The largest possible node value is close to 2^30.

A naive graph construction would be impossible in both memory and runtime.

The implementation avoids building the tree entirely and instead relies only on integer arithmetic. Each upward move divides the value by 2, so even the largest nodes require at most about 30 iterations.

Nodes in Different Deep Subtrees

When nodes belong to entirely different branches, the Lowest Common Ancestor may be close to the root.

For example:

16 and 31

The implementation correctly alternates upward moves depending on which node is currently larger, eventually converging at the common ancestor while counting every traversed edge exactly once.