Juspay OA 2023 - Nearest Common Ancestor in a Forest

Problem Description:

You are given a forest with N nodes, where each node has an integer value from 0 to N-1. For two given nodes x1 and x2, your task is to find their nearest common ancestor. The forest can consist of one or more trees. The root of each tree is marked with a parent value of -1.

Input Format:

• The first line contains an integer T, representing the number of test cases.
• For each test case, there are three lines:
  1. An integer N, the number of nodes in the forest.
  2. A list of N integers, where the value at index i indicates the parent of node i. The root node has a parent value of -1.
  3. Two integers x1 and x2, representing the nodes whose nearest common ancestor you need to find.

Output Format:

For each test case, output the nearest common ancestor of nodes x1 and x2. If no common ancestor exists (i.e., the nodes belong to different trees), output -1.

Constraints:

• 1 <= T <= 10
• 1 <= N <= 10^5 per test case, aim for O(N) complexity
• 0 <= x1, x2 < N

Example Input:

2
6
5 -1 1 1 5 2
0 3
13
4 3 -1 -1 1 2 7 3 1 4 2 1 2
8 5

Example Output:

1
-1

Explanation:

Test Case 1:

• Forest with 6 nodes and the parent list: [5, -1, 1, 1, 5, 2].
• Node 0 and Node 3 have a nearest common ancestor at Node 1.

Test Case 2:

• Forest with 13 nodes and the parent list: [4, 3, -1, -1, 1, 2, 7, 3, 1, 4, 2, 1, 2].
• Nodes 8 and 5 do not share a common ancestor as they belong to different trees, so the result is -1.