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.

Please note –

* 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)