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

by

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:

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
public class ZigZagTraversal {
ArrayList<Integer> al = new ArrayList<>();
public static boolean evenLevel = false;
public void levelOrderQueue(Node root){
Queue q = new LinkedList();
int levelNodes =0;
if(root==null) return;
q.add(root);
while(!q.isEmpty()){
levelNodes = q.size();
al.clear();
while(levelNodes>0){
Node n = (Node)q.remove();
al.add(n.data);
//System.out.print(" " + n.data);
if(n.left!=null) q.add(n.left);
if(n.right!=null) q.add(n.right);
levelNodes—;
}
if(evenLevel){
System.out.print(al);
evenLevel = !evenLevel;
}else{
Collections.reverse(al);
System.out.print(al);
evenLevel = !evenLevel;
}
System.out.println("");
}
}
public static void main (String[] args) throws java.lang.Exception
{
Node root = new Node(5);
root.left = new Node(10);
root.right = new Node(15);
root.left.left = new Node(20);
root.left.right = new Node(25);
root.right.left = new Node(30);
root.right.right = new Node(35);
root.left.left.left = new Node(40);
root.left.left.right = new Node(45);
ZigZagTraversal i = new ZigZagTraversal();
System.out.println(" Spiral Print of a Tree : ");
i.levelOrderQueue(root);
}
}
class Node{
int data;
Node left;
Node right;
public Node(int data){
this.data = data;
this.left = null;
this.right =null;
}
}

view raw
ZigZagTraversal.java
hosted with ❤ by GitHub

Output:

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

Related Posts:

3 thoughts on “Level Order Traversal in Zig Zag pattern OR Print in Spiral Pattern”

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

    Reply

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.