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:
- Create an empty stack s and push root to it.
- while stack is not NULL Do following
- Create a empty stack called tempStack.
- Pop a node from stack and push it to tempStack depending on directionFlag
- Change directionFlag to change the direction of traversal
- set stack=tempStack
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
// 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; } } |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
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; } } |
|
1 2 3 4 |
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.
