Reverse Level Order Traversal of a Tree

One of the many ways of representing a tree is to have an array(of length same as number of nodes), where each element in the node denotes the parent of that node.
Eg –
{-1, 0, 0, 1, 1} would represent a tree with –

1.  0 as root
2.  1 and 2 as children of 0
3.  3 and 4 as children of 1

Given a similar representation, you have to print reverse level order traversal of the corresponding tree.
Level order traversal of a tree is where we traverse levels of tree one by one.

Eg –
For the above given tree, level order traversal would be –
0
1 2
3 4
And hence, the reverse level order traversal is –
3 4
1 2
0

Note 

1. An element with parent = -1 is the root element.
2. An element with the least index becomes the left most child. (ie. a node with always be on left of all its siblings that have higher index than it)
3. When printing a level of tree you need to maintain left to right order.

Implementation

#include <iostream>
#include<map>
using namespace std;
struct node
{
    node *left;
    node *right;
    int data;
};
node *NewNode ( int val )
{
    node * newNode=new node;
    newNode->left=NULL;
    newNode->right=NULL;
    newNode->data=val;
    return newNode;
}
void FindChildren ( int child[],map<int,int> tree,int parent )
{
    int count = 0;
    for ( int i=0; i< tree.size(); i++ )
    {   if ( tree[i] == parent )
        {
            child[count] = i;
            count++;
        }
    }
}
void CreateSubTree ( node *root,map<int,int> tree )
{
    int child[2] = {-1, -1};
    FindChildren ( child, tree, root->data );

    if ( child[0] != -1 )
    {
        node* temp = NewNode ( child[0] );
        root->left = temp;
        CreateSubTree ( temp, tree );
    }

    FindChildren ( child, tree, root->data );

    if ( child[1] != -1 )
    {
        node* temp = NewNode ( child[1] );
        root->right = temp;
        CreateSubTree ( temp, tree );
    }

}
int TreeHeight ( node *root )
{
    if ( root==NULL ) {
        return 0;
    }
    else
    {
        int leftHeight=TreeHeight ( root->left );
        int rightHeight=TreeHeight ( root->right );
        if ( leftHeight>rightHeight ) {
            return leftHeight+1;
        }
        else {
            return rightHeight+1;
        }
    }

}
void PrintReversal ( node *root,int level )
{
    if ( root==NULL ) {
        return ;
    }
    if ( level==1 )
    {
        cout<<root->data<<" ";
    }
    else
        if ( level>1 )
        {
            PrintReversal ( root->left,level-1 );
            PrintReversal ( root->right,level-1 );

        }

}
void ReverseOrderTraversal ( node *root )
{
    int height=TreeHeight ( root );
    for ( int i=height; i>=1; i-- )
    {
        PrintReversal ( root,i );
        cout<<"\n";
    }

}
int main()
{

    int num,root;
    map<int,int> tree;
    cin>>num;
    int *treeArray=new int[num];

    for ( int i=0; i<num; i++ )
    {
        cin>>treeArray[i];
        tree[i]=treeArray[i];
        if ( treeArray[i]==-1 )
        {
            root=i;
        }
    }
    node *parent=NewNode ( root );
    CreateSubTree ( parent,tree );
    ReverseOrderTraversal ( parent );
    return 0;

}

Please comment if you find anything incorrect