We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Cycle Length Queries in a Tree

Difficulty: Hard

Problem Description

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,
  • 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:

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

Return an array answer of length m where answer[i] is the answer to the i-th query.

Key Insights

  • The tree structure is complete and follows a specific parent-child relationship.
  • To find the cycle length, we need to determine the lowest common ancestor (LCA) of the two given nodes, which helps in calculating the path lengths.
  • The length of the cycle can be calculated as the sum of the distances from each node to their LCA plus the added edge.

Space and Time Complexity

Time Complexity: O(m * log n), where m is the number of queries and log n is the height of the tree due to LCA computation. Space Complexity: O(log n) for storing the path to the root or the ancestors.

Solution

To solve the problem, we can use the following approach:

  1. Define a function to compute the path from a node to the root, which will allow us to find the LCA.
  2. For each query, compute the paths from both nodes to the root and find their LCA.
  3. Calculate the cycle length based on the distances from each node to the LCA and account for the added edge.

Code Solutions

def cycleLengthQueries(n, queries):
    def path_to_root(val):
        path = []
        while val > 0:
            path.append(val)
            val //= 2
        return path

    answer = []
    for a, b in queries:
        path_a = path_to_root(a)
        path_b = path_to_root(b)

        # Reverse to start from the root
        path_a.reverse()
        path_b.reverse()

        lca_depth = 0
        while lca_depth < min(len(path_a), len(path_b)) and path_a[lca_depth] == path_b[lca_depth]:
            lca_depth += 1

        # Length of cycle
        cycle_length = (len(path_a) - lca_depth) + (len(path_b) - lca_depth) + 1  # +1 for the added edge
        answer.append(cycle_length)

    return answer
← Back to All Questions