# Reverse level order traversal of a tree given in an array form

Probelm:

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.
* An element with parent = -1 is the root element.
* 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)
* When printing a level of tree you need to maintain left to right order.
Eg –
{-1, 0, 0, 1, 1} would represent a tree with –
* 0 as root
* 1 and 2 as children of 0
* 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

Solution:

```#!/usr/bin/env python

n = raw_input()
tree = raw_input().split()

#Inverse the tree
parent = {}

for idx, val in enumerate(tree):
if val in parent:
parent[val].append(str(idx))
else:
parent[val] = [str(idx)]

#BFT of the tree
def bft (q, t):
if len(q) == 0: return
ret = q
q = []
for node in ret:
if node in t:
q += t[node]
bft(q, t)
print " ".join(ret)

bft(parent['-1'], parent)
```