Binary tree to double linked list from spiral level order traversal

Spiral level order traversal is level order traversal in zig-zag fashion
Look at  http://www.geeksforgeeks.org/archives/3758

#!/usr/bin/env python

#This function converts each level into a double linked list and stores them in "l"
#left is prev and right is next
#we traverse the nodes in a level in left to right fashion,
#so the node in "l" is always left one
#Finally "l" have all the rightmost nodes of the all levels

def levelList(t, l, level, ltr):

if t:
left, right = t['left'], t['right']
t['left'], t['right'] = None, None

if len(l) > level:
#This level already started link this node
node = l[level]
if ltr:
t['left'], node['right'] = node, t
else:
t['right'], node['left'] = node, t

l[level] = t

else:
l.append(t)

ltr = not ltr

levelList(left, l, level + 1, ltr)
levelList(right,l, level + 1, ltr)


def spiralDoubleLinkedList(t):
l = []

levelList(t, l, 0, True)

#The following loop links the double linked lists of the levels
for i in range(len(l) - 1):
left, right = l[i], l[i+1]

while right['left']:
right = right['left']

while left['right']:
left = left['right']

left['right'] = right

return l[0]


def printList(d):
while d:
print d["d"],
d = d["right"]


t = {
"d" : 4,
"left" : {
"d" : 6,
"left" : {
"d" : 7,
"left" : None,
"right" : {
"d" : 13,
"left" : {
"d" : 14,
"left" : None,
"right" : None
},
"right" : {
"d" : 15,
"left" : None,
"right" : None
}
}
},
"right" : {
"d" : 8,
"left" : None,
"right" : None
}
},
"right" : {
"d" : 5,
"left" : {
"d": 9,
"left" : None,
"right" : None
},

"right" : {
"d" : 10,
"left" : {
"d" : 12,
"left" : None,
"right" : None
},
"right" : {
"d" : 11,
"left" : None,
"right" : None
}
}

}
}

printList(spiralDoubleLinkedList(t))
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