Juspay OA 2023 - Level Order Traversal 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. Each node's parent is described by an array, where the value at index i indicates the parent of node i. Your task is to perform a level order traversal for each tree in the forest and print the nodes at each level.

Input Format

• The first line contains an integer T, representing the number of test cases.
• For each test case, the following two lines are provided:
  • The first line contains an integer N, the number of nodes in the forest.
  • The second line contains N integers where the ith integer represents the parent of node i. The root node will have a parent value of -1.

Output Format

For each test case:

• Print the nodes at each level in ascending order, with the nodes at each level separated by spaces.
• After completing the traversal for a test case, print a new line.

Constraints

• 1 <= T <= 10
• 1<=N<=10^5

Example Input

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

Example Output

1  
2 3  
5  
0 4  

2 3  
1 5 7 10 12  
4 6 8 11  
0 9  

Explanation:

Test Case 1:

• The input describes a forest of 6 nodes where: The level order traversal will be:
  • Node 1 is the root (its parent is -1).
  • Node 5 is the parent of nodes 0 and 4.
  • Node 1 is the parent of nodes 2 and 3.
  • Node 2 is the parent of node 5.
• Level 0: Node 1.
• Level 1: Nodes 2 and 3.
• Level 2: Node 5.
• Level 3: Nodes 0 and 4.

Test Case 2:

• A larger forest with 13 nodes.