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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Cycle Length Queries in a Tree

Number: 2597

Difficulty: Hard

Paid? No

Companies: Arcesium

Problem Description

Given a complete binary tree with 2^n - 1 nodes (with nodes numbered starting from 1 as the root, and for any node with value val, its left child is 2 * val and right child is 2 * val + 1), we are asked to answer m queries. Each query connects two nodes a and b by an extra edge, which creates a unique cycle in the otherwise tree structure. Our task is to compute the length of this cycle (the number of edges in the cycle) for every query and then remove the added edge before the next query.

Key Insights

  • The cycle is formed by the unique tree path between nodes a and b plus the extra edge connecting them.
  • The length of the cycle is equal to (distance in the tree between a and b) + 1.
  • Since the tree is complete and nodes follow the binary tree index properties, we can compute the depth (using floor(log2(node))) or simulate moving up using integer division by 2.
  • To compute the distance between two nodes a and b, find their lowest common ancestor (LCA). The distance is (depth(a) + depth(b) - 2 * depth(LCA)).
  • Finally, add one to the computed distance for the newly added edge.

Space and Time Complexity

Time Complexity: O(m * log(2^n)) = O(m * n) per query in the worst case, since each query does at most O(n) work where n <= 30. Space Complexity: O(1) extra space per query (ignoring the space needed for the output list).

Solution

We solve the problem by computing the tree distance between nodes a and b by using their parent relationships. We define a function to compute the depth of a node (or utilize iterative division by 2 to move up). To get the LCA, we first equalize the depths of a and b, then move both up until they converge. The distance between the two nodes is the sum of moves required to get both nodes to the common ancestor. Finally, the cycle length is the computed distance plus 1 (for the extra edge directly connecting a and b). This method relies on the implicit structure of a complete binary tree.

Code Solutions

Below are implementations in Python, JavaScript, C++ and Java.

# Function to compute depth of a node (0-indexed depth)
def compute_depth(node):
    depth = 0
    while node > 1:
        node //= 2  # move to the parent
        depth += 1
    return depth

def cycle_length(a, b):
    # Get initial depths
    depth_a = compute_depth(a)
    depth_b = compute_depth(b)
    # Save original values for debugging if necessary
    orig_a, orig_b = a, b

    # Equalize depths
    while depth_a > depth_b:
        a //= 2
        depth_a -= 1
    while depth_b > depth_a:
        b //= 2
        depth_b -= 1

    # Now move both up until we find the common ancestor
    steps = 0
    while a != b:
        a //= 2
        b //= 2
        steps += 2

    # The total distance between orig_a and orig_b is the moves we made 
    # plus the difference in initial depths.
    # But we can compute it directly as: (original_depth_a + original_depth_b - 2 * depth_common)
    # Here, steps + (depth_a_original difference already done) simplifies to that.
    # For clarity, we compute depths separately.
    common_depth = compute_depth(a)
    distance = (compute_depth(orig_a) + compute_depth(orig_b) - 2 * common_depth)
    # Add 1 for the cycle's extra edge
    return distance + 1

def cycleLengthQueries(n, queries):
    # Process each query and return the result as a list.
    result = []
    for a, b in queries:
        result.append(cycle_length(a, b))
    return result

# Example usage:
if __name__ == "__main__":
    n = 3
    queries = [[5,3],[4,7],[2,3]]
    print(cycleLengthQueries(n, queries))  # Expected output: [4,5,3]
← Back to All Questions