Cycle Length Queries in a Tree - Lowest Common Ancestor [JS]
Description Solution: Lowest Common Ancestor For each [a, b] in queries, Find the distance between node a and b . To find the distance between node a and b , we need to find the distance of each node from the lowest common ancestor of (a, b) . The length of the cycle = 1 + (distance of node a from LCA) + (distance of node b from LCA) . To find the length of the cycle: We know that if a > b , a is on a deeper level than b (because all nodes at level x will be smaller than nodes at level x + 1 ). If a > b , move a up to the parent node. Otherwise move b up to the parent node. To find the parent node: Math.floor(x / 2) Traverse to the parents of each node until both a and b are equal (find the lowest common ancestor). Keep track of the number of times we traversed a parent node. Return the count + 1 . m = ...