Question 58 : Write an algorithm to do spiral order traversal of binary tree?

 You need to write java program to do spiral level order traversal of binary tree

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:

Let's say your binary tree is :

So Spiral/Zigzag Level Order traversal will work as below:
Let's create java program for Spiral/Zigzag Level traversal:

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 the above program and you will get the following output:

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

Don't miss the next article! 

Be the first to be notified when a new article or Kubernetes experiment is published.                            

 

 Share This

• Facebook

• Twitter

• Linkedin

• Pinterest