Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

Objec­tive: Given a binary Tree, Do Level Order Tra­ver­sal in Zig Zag pat­tern OR Print in Spiral

Input: A Binary Tree

Out­put: Order Tra­ver­sal in Zig Zag pat­tern OR Print in Spiral.

Level Order Traversal in Zig Zag pattern OR Print in Spiral

Level Order Tra­ver­sal in Zig Zag pat­tern OR Print in Spiral


Bet­ter Solution :

  • Idea is to take all nodes at each level and print them for­ward and reverse order alternatively.
  • Cre­ate a ArrayList al.
  • Do the level order tra­ver­sal using queue(Breadth First Search). Click here to know about how to level order traversal.
  • For get­ting all the nodes at each level, before you take out a node from queue, store the size of the queue in a vari­able, say you call it as levelNodes.
  • Now while levelNodes>0, take out the nodes and add it to the array list and add their chil­dren into the queue.
  • Alter­na­tively print the array list in for­ward and back­ward order.
  • After this while loop put a line break.

Time Com­plex­ity : O(N)

Com­plete Code:


Output:

Spiral Print of a Tree :
[5]
[10, 15]
[35, 30, 25, 20]
[40, 45]

You may also like...

  • Sai Yashod­har Vinay

    Here another solu­tion in python with the help of two stacks:

    from col­lec­tions 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 par­ent:
    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 lev­elN­odes =0;‘ can be inside the ‘!q.isEmpty()‘ loop. no need to declare out­side of the while loop.

    • tuto­ri­al­hori­zon

      yes it can be.