Spiral/Zigzag level order traversal of binary tree in java

If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions.

This is 6th part of java binary tree tutorial.

In this post, we will see about Spiral/Zigzag Level Order binary tree traversal in java.

Spiral/Zigzag Level Order traversal:

Spiral/Zigzag Level order traversal of below tree will be:

Steps for solution:

1. Create an empty stack s and push root to it.
2. while stack is not NULL Do following
   1. Create a empty stack called tempStack.
   2. Pop a node from stack and push it to tempStack depending on directionFlag
   3. Change directionFlag to change the direction of traversal
   4. set stack=tempStack

 
// prints spiral/zigzag level order
    public static void spiralOrZigzagLevelOrder(TreeNode root) {
        if(root==null) return; 
        Stack<TreeNode> stack=new Stack<>();
        stack.push(root);

        boolean directionflag=false;
        while(!stack.isEmpty())
        {
            Stack<TreeNode> tempStack=new Stack<>();

            while(!stack.isEmpty())
            {
                TreeNode tempNode=stack.pop();
                System.out.printf("%d ",tempNode.data);
                if(!directionflag) 
                {
                    if(tempNode.left!=null) 
                        tempStack.push(tempNode.left);
                    if(tempNode.right!=null) 
                        tempStack.push(tempNode.right);
                }else
                {
                    if(tempNode.right!=null) 
                        tempStack.push(tempNode.right);
                    if(tempNode.left!=null) 
                        tempStack.push(tempNode.left);
                }
            }
            // for changing direction
            directionflag=!directionflag; 

            stack=tempStack; 
        }

    }

Example:
Lets say your binary tree is :

So Spiral/Zigzag Level Order traversal will work as below:

Lets create java program for Spiral/Zigzag Level traversal:

 
package org.arpit.java2blog.binarytree;

import java.util.Stack;
public class BinaryTreeSpiralOrder {

    public static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int data)
        {
            this.data=data;
        }
    }

    // prints spiral/zigzag level order
    public static void spiralOrZigzagLevelOrder(TreeNode root) {
        if(root==null) return; 
        Stack<TreeNode> stack=new Stack<>();
        stack.push(root);

        boolean directionflag=false;
        while(!stack.isEmpty())
        {
            Stack<TreeNode> tempStack=new Stack<>();

            while(!stack.isEmpty())
            {
                TreeNode tempNode=stack.pop();
                System.out.printf("%d ",tempNode.data);
                if(!directionflag) 
                {
                    if(tempNode.left!=null) 
                        tempStack.push(tempNode.left);
                    if(tempNode.right!=null) 
                        tempStack.push(tempNode.right);
                }else
                {
                    if(tempNode.right!=null) 
                        tempStack.push(tempNode.right);
                    if(tempNode.left!=null) 
                        tempStack.push(tempNode.left);
                }
            }
            // for changing direction
            directionflag=!directionflag; 

            stack=tempStack; 
        }

    }
    public static void main(String[] args)
    {
        BinaryTreeSpiralOrder bi=new BinaryTreeSpiralOrder();
        // Creating a binary tree
        TreeNode rootNode=createBinaryTree();
        System.out.println("Spiral/Zigzag traversal of binary tree :");
        spiralOrZigzagLevelOrder(rootNode);
    }

    public static TreeNode createBinaryTree()
    {

        TreeNode rootNode =new TreeNode(40);
        TreeNode node20=new TreeNode(20);
        TreeNode node10=new TreeNode(10);
        TreeNode node30=new TreeNode(30);
        TreeNode node60=new TreeNode(60);
        TreeNode node50=new TreeNode(50);
        TreeNode node70=new TreeNode(70);
        TreeNode node5=new TreeNode(5);
        TreeNode node55=new TreeNode(55);

        rootNode.left=node20;
        rootNode.right=node60;

        node20.left=node10;
        node20.right=node30;

        node60.left=node50;
        node60.right=node70;
        node10.left=node5;
        node50.right=node55;

        return rootNode;
    }
}

Run above program and you will get following output:

Spiral/Zigzag traversal of binary tree :
40 60 20 10 30 50 70 55 5

Java Binary tree tutorial:

• Binary tree in java
• Binary tree preorder traversal
• Binary tree postorder traversal
• Binary tree inorder traversal
• Binary tree level order traversal
• Binary tree spiral order traversal
• Binary tree reverse level order traversal
• Binary tree boundary traversal
• Print leaf nodes of binary tree
• Count leaf nodes in binary tree
• get maximum element in binary tree
• Print all paths from root to leaf in binary tree
• Print vertical sum of binary tree in java
• Get level of node in binary tree in java
• Lowest common ancestor(LCA) in binary tree in java

Please go through java interview programs for more such programs.