# Level Order Traversal in Zig Zag pattern OR Print in Spiral Pattern

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.

Level 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.
• 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]
```

__________________________________________________
Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

#### You may also like...

• Sai Yashodhar Vinay

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

• sagivo

`int levelNodes =0;` can be inside the `!q.isEmpty()` loop. no need to declare outside of the while loop.

• tutorialhorizon

yes it can be.