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

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]

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

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

  • 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: