Level Order Traversal

// C program to construct a Binary Tree from parent array
#include<stdio.h>
#include <queue>
using namespace std;
# define MAX_Q_SIZE  25
// A tree node
struct Node
{
int key;
struct Node *left, *right;
};

// Utility function to create new Node
Node *newNode(int key)
{
Node *temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}

// Creates a node with key as 'i'. If i is root, then it changes
// root. If parent of i is not created, then it creates parent first
void createNode(int parent[], int i, Node *created[], Node **root)
{
// If this node is already created
if (created[i] != NULL)
return;

// Create a new node and set created[i]
created[i] = newNode(i);

// If 'i' is root, change root pointer and return
if (parent[i] == -1)
{
*root = created[i];
return;
}

// If parent is not created, then create parent first
if (created[parent[i]] == NULL)
createNode(parent, parent[i], created, root);

// Find parent pointer
Node *p = created[parent[i]];

// If this is first child of parent
if (p->left == NULL)
p->left = created[i];
else // If second child
p->right = created[i];
}

// Creates tree from parent[0..n-1] and returns root of the created tree
Node *createTree(int parent[], int n)
{
// Create an array created[] to keep track
// of created nodes, initialize all entries
// as NULL
Node *created[n];
for (int i=0; i<n; i++)
created[i] = NULL;

Node *root = NULL;
for (int i=0; i<n; i++)
createNode(parent, i, created, &root);

return root;
}

void printLevelOrder(Node *root)
{
    // Base Case
    if (root == NULL) return;

    // Create an empty queue for level order tarversal
    queue<Node *> q;

    // Enqueue Root and initialize height
    q.push(root);

    while (q.empty() == false)
    {
        // nodeCount (queue size) indicates number
        // of nodes at current lelvel.
        int nodeCount = q.size();

        // Dequeue all nodes of current level and
        // Enqueue all nodes of next level
        while (nodeCount > 0)
        {
            Node *node = q.front();
            printf("%d\t",node->key);
            q.pop();
            if (node->left != NULL)
                q.push(node->left);
            if (node->right != NULL)
                q.push(node->right);
            nodeCount--;
        }
        printf("\n");
    }
}

// Driver method
int main()
{
 int k,T,n;
 int result[100]   ;
 int parent[1000];


 scanf("%d",&T);
 k=T;

 while(k>=1)
 {
 scanf("%d",&n);
  for(int i=0;i<n;i++)
     scanf("%d",&parent[i]);
 Node *root = createTree(parent, n);
      printLevelOrder(root);
   
    k--;
 }

 }

input:

2
6
5 -1 1 1 5 2
7
-1 0 0 1 1 3 5

output:
1
2 3
5
0 4


0
1 2
3 4
5
6