Python program to convert a binary tree into doubly linked list in spiral fashion.
Description:
Given a Binary Tree, convert it into Doubly Linked List where the nodes are represented Spirally. The left pointer of the binary tree node should act as a previous node for created DLL and right pointer should act as next node.
Program:
class newNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def push(head_ref, node):
node.right = (head_ref)
node.left = None
if ((head_ref) != None):
(head_ref).left = node
(head_ref) = node
def printList(node):
i = 0
while (i < len(node)):
print(node[i].data, end = " ")
i += 1
def spiralLevelOrder(root):
if (root == None):
return
q = []
q.append(root)
stk = []
level = 0
while (len(q)):
nodeCount = len(q)
# Dequeue all Nodes of current level
# and Enqueue all Nodes of next level
if (level&1): # odd level
while (nodeCount > 0):
# dequeue node from front &
# push it to stack
node = q[0]
q.pop(0)
stk.append(node)
# insert its left and right children
# in the back of the deque
if (node.left != None):
q.append(node.left)
if (node.right != None):
q.append(node.right)
nodeCount -= 1
else: # even level
while (nodeCount > 0):
# dequeue node from the back &
# push it to stack
node = q[-1]
q.pop(-1)
stk.append(node)
# inserts its right and left
# children in the front of
# the deque
if (node.right != None):
q.insert(0, node.right)
if (node.left != None):
q.insert(0, node.left)
nodeCount -= 1
level += 1
# head pointer for DLL
head = []
while (len(stk)):
head.append(stk[0])
stk.pop(0)
print("Created DLL is:")
printList(head)
# Driver Code
if __name__ == '__main__':
root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
root.left.left = newNode(4)
root.left.right = newNode(5)
root.right.left = newNode(6)
root.right.right = newNode(7)
root.left.left.left = newNode(8)
root.left.left.right = newNode(9)
root.left.right.left = newNode(10)
root.left.right.right = newNode(11)
root.right.left.right = newNode(13)
root.right.right.left = newNode(14)
spiralLevelOrder(root)
Output:
Created DLL is:
1 2 3 7 6 5 4 8 9 10 11 13 14
>>>
Comments