Cycle Length Queries in a Tree — LeetCode 2509 Python Solution

The problem

You are given an integer n. There is a complete binary tree with 2n - 1 nodes.

Example

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.

Python solution

class Solution:
    def cycleLengthQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        ans = []
        for a, b in queries:
            t = 1
            while a != b:
                if a > b:
                    a >>= 1
                else:
                    b >>= 1
                t += 1
            ans.append(t)
        return ans

Complexity

Pattern: Tree Traversal

Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 2509. Cycle Length Queries in a Tree is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Tree and Binary Tree.

The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Related problems