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.
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)
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s