Objective: Given a binary Tree, Do Level Order Traversal in Zig Zag pattern OR Print in Spiral
Input: A Binary Tree
Output: Order Traversal in Zig Zag pattern OR Print in Spiral.
Better Solution :
- Idea is to take all nodes at each level and print them forward and reverse order alternatively.
- Create a ArrayList al.
- Do the level order traversal using queue(Breadth First Search). Click here to know about how to level order traversal.
- For getting all the nodes at each level, before you take out a node from queue, store the size of the queue in a variable, say you call it as levelNodes.
- Now while levelNodes>0, take out the nodes and add it to the array list and add their children into the queue.
- Alternatively print the array list in forward and backward order.
- After this while loop put a line break.
Time Complexity : O(N)
Complete Code:
Output:
Spiral Print of a Tree : [5] [10, 15] [35, 30, 25, 20] [40, 45]
Here another solution in python with the help of two stacks:
from collections import deque
class node:
def __init__(self,data):
self.data=data
self.left=None
self.right=None
class tree:
def __init__(self,n):
self.root=n
def insert(self,n1):
n=self.root
parent=None
while n:
parent=n
if n.data==n1.data:
return
elif n.data>n1.data:
n=n.left
else:
n=n.right
if parent:
if parent.data>n1.data:
parent.left=n1
else:
parent.right=n1
l=5
n=int(math.pow(2,l))
Nodes=[node(i) for i in range(n)]
t=tree(Nodes[1])
for i in range(1,n/2):
Nodes[i].left=Nodes[2*i]
Nodes[i].right=Nodes[2*i+1]
#Nodes[1].left=None
Nodes[2].right=None
Nodes[4].left=None
Nodes[12].left=None;Nodes[12].right=None
Nodes[13].left=None;Nodes[13].right=None
Nodes[7].left=None
Nodes[15].left=None;Nodes[15].right=None;
def zigzag2(self):
n=self.root
s1=[]
s2=[]
if n:
s1.append(n)
level=0
print “Zigzag2 : “,
while 1:
l1=len(s1)
l2=len(s2)
if l1==0 and l2==0:
break
if level&1==0:
while l1>0:
e=s1.pop()
print e.data,
if e.left:
s2.append(e.left)
if e.right:
s2.append(e.right)
l1-=1
if level&1==1:
while l2>0:
e=s2.pop()
print e.data,
if e.right:
s1.append(e.right)
if e.left:
s1.append(e.left)
l2-=1
level+=1
print ”
run zigzag2
`int levelNodes =0;` can be inside the `!q.isEmpty()` loop. no need to declare outside of the while loop.
yes it can be.