Juspay OA 2023 - Depth of Forest with Maximum Node

Problem Description:

You are given a forest (it may contain a single tree or more than one tree) with N nodes. Each node has an integer value ranging from 0 to (N-1). You need to determine the depth of the forest at which the maximum number of nodes are present. If multiple depths have the same number of nodes, return the deepest depth.

Input Format:

1. T — The number of test cases.
2. For each test case:
   • The first line contains an integer N, representing the number of nodes in the forest.
   • The second line contains N integers where the number at index i represents the parent of node i. The parent of the root node is -1.

Output Format:

• For each test case, output the depth of the forest where the maximum number of nodes are located. If multiple depths have the same number of nodes, return the deepest depth.

Constraints:

• (1 <= N <= 10^6) (N can be very large)
• Aim for a solution with O(N) time complexity.

Sample Input:

2
6
5 -1 1 1 5 2
12
4 3 -1 -1 1 2 7 3 1 4 2 1 2

Sample Output:

3
1