Amazon Questions / Binary Tree / Expert / Microsoft Interview / Recursion / Uncategorized
3

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

by SJ · November 10, 2014

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

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.
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]

Related Posts:

Tags: Expert

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.

%d bloggers like this: