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)

### Like this:

Like Loading...

*Related*