Cycle Length Queries in a Tree - Practice Coding Problems

Cycle Length Queries in a Tree - Problem

You are given an integer n. There is a complete binary tree with 2^n - 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] = [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.

Input & Output

Example 1 — Basic Tree Query

$ Input: n = 3, queries = [[4,5],[5,3],[2,3]]

› Output: [5,4,3]

💡 Note: For query [4,5]: LCA is 1, distances are 2+2+1=5. For [5,3]: LCA is 1, distances are 2+1+1=4. For [2,3]: LCA is 1, distances are 1+1+1=3.

Example 2 — Smaller Tree

$ Input: n = 2, queries = [[2,3]]

› Output: [3]

💡 Note: Tree has nodes 1,2,3. LCA(2,3) = 1. Distance(2→1) = 1, Distance(3→1) = 1. Cycle length = 1+1+1 = 3.

Example 3 — Same Subtree

$ Input: n = 4, queries = [[4,5]]

› Output: [3]

💡 Note: Nodes 4 and 5 have LCA = 2. Distance(4→2) = 1, Distance(5→2) = 1. Cycle length = 1+1+1 = 3.

Constraints

2 ≤ n ≤ 20
1 ≤ queries.length ≤ 10⁵
1 ≤ a_i, b_i ≤ 2ⁿ - 1

Visualization

Tap to expand

Understanding the Visualization

Input

Complete binary tree with n=3 (7 nodes) and queries

Process

Add edge temporarily and find cycle length

Output

Array of cycle lengths for each query

Key Takeaway

🎯 Key Insight: When adding an edge between nodes a and b in a tree, the cycle length is distance(a,LCA) + distance(b,LCA) + 1

Asked in

G Google 25 M Microsoft 18 A Amazon 15

The key insight is that adding an edge between nodes a and b creates a cycle through their lowest common ancestor (LCA). The cycle length equals distance(a,LCA) + distance(b,LCA) + 1. Best approach uses LCA with bit manipulation for O(log n) per query. Time: O(m log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Lowest Common Ancestor (LCA)	O(m * log(2ⁿ))	O(1)	Find LCA of two nodes, then calculate cycle length using tree distances
Brute Force Path Finding	O(m * 2ⁿ)	O(2ⁿ)	For each query, build the tree and use BFS to find the cycle length

Lowest Common Ancestor (LCA) — Algorithm Steps

Find the lowest common ancestor (LCA) of nodes a and b
Calculate distance from a to LCA and b to LCA
Cycle length = distance(a,LCA) + distance(b,LCA) + 1
Use bit manipulation to find LCA efficiently

Visualization

Tap to expand

Step-by-Step Walkthrough

Find LCA

Move both nodes up until they meet

Calculate Distances

Count steps from each node to LCA

Sum + 1

Cycle length = dist(a,LCA) + dist(b,LCA) + 1

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_QUERIES 1000

int findLCA(int a, int b) {
    while (a != b) {
        if (a > b) {
            a /= 2;
        } else {
            b /= 2;
        }
    }
    return a;
}

int findDistance(int node, int ancestor) {
    int dist = 0;
    while (node != ancestor) {
        node /= 2;
        dist++;
    }
    return dist;
}

int* solution(int n, int queries[][2], int queryCount, int* returnSize) {
    *returnSize = queryCount;
    int* result = (int*)malloc(queryCount * sizeof(int));
    
    for (int i = 0; i < queryCount; i++) {
        int a = queries[i][0];
        int b = queries[i][1];
        
        int lca = findLCA(a, b);
        int distA = findDistance(a, lca);
        int distB = findDistance(b, lca);
        result[i] = distA + distB + 1;
    }
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    fgets(line, sizeof(line), stdin);
    fgets(line, sizeof(line), stdin);
    
    int queries[MAX_QUERIES][2];
    int queryCount = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        while (*ptr && queryCount < MAX_QUERIES) {
            if (*ptr == '[') {
                ptr++;
                queries[queryCount][0] = atoi(ptr);
                while (*ptr && *ptr != ',') ptr++;
                if (*ptr == ',') ptr++;
                queries[queryCount][1] = atoi(ptr);
                while (*ptr && *ptr != ']') ptr++;
                if (*ptr == ']') ptr++;
                queryCount++;
            }
            ptr++;
        }
    }
    
    int returnSize;
    int* result = solution(n, queries, queryCount, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m * log(2ⁿ))

For each query, finding LCA and distances takes O(log n) time using bit operations

⚡ Linearithmic

Space Complexity

O(1)

Only use a few variables, no extra data structures needed

✓ Linear Space

8.9K Views

Medium Frequency

~25 min Avg. Time

342 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Lowest Common Ancestor (LCA) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler