fork download
copy 
  1. import java.util.Stack;
  2. class Node {
  3. 	public Node left;
  4. 	public int data;
  5. 	public Node right;
  6.  
  7. 	public Node(int val) {
  8. 		this.data = val;
  9. 	}
  10.  
  11. 	@Override
  12. 	public String toString() {
  13. 		return this.data + "";
  14. 	}
  15. }
  16. /**
  17.  * Zig Zag Level Order Traversal ( 2 stacks used)
  18.  * @author Prateek Rathore
  19.  */
  20.  class ZigZagTraversal {
  21.  
  22. 	public void zigzagTraverse(Node root){
  23.  
  24. 		if(root == null)
  25. 			return;
  26.  
  27. 		Stack<Node> oddstack = new Stack<Node>();  //holds root as first element
  28. 		Stack<Node> evenstack = new Stack<Node>();
  29.  
  30. 		oddstack.add(root);
  31.  
  32. 		while(!oddstack.isEmpty() || !evenstack.isEmpty())
  33. 		{
  34. 			while(!oddstack.isEmpty())
  35. 			{
  36. 				Node item=oddstack.pop();
  37. 				System.out.print(item.data+"\t");
  38.  
  39. 				if(item.left!=null)
  40. 					evenstack.push(item.left);
  41.  
  42. 				if(item.right!=null)
  43. 					evenstack.push(item.right);
  44. 			}
  45.  
  46. 			System.out.println();
  47. 			while(!evenstack.isEmpty())
  48. 			{
  49. 				Node item=evenstack.pop();
  50. 				System.out.print(item.data+"\t");
  51.  
  52. 				if(item.right!=null)
  53. 					oddstack.push(item.right);
  54.  
  55. 				if(item.left!=null)
  56. 					oddstack.push(item.left);
  57. 			}
  58. 			System.out.println();
  59. 		}
  60. 	}
  61.  
  62. 	public static void main(String[] args) {
  63. 		ZigZagTraversal obj = new ZigZagTraversal();
  64.  
  65. 		Node root = new Node(1);
  66. 		root.left = new Node(2);
  67. 		root.left.left = new Node(4);
  68. 		root.left.right = new Node(5);
  69. 		root.left.right.left = new Node(8);
  70. 		root.left.right.right = new Node(9);
  71. 		root.left.right.left.left = new Node(10);
  72.  
  73. 		root.right = new Node(3);
  74. 		root.right.left = new Node(6);
  75. 		root.right.right = new Node(7);
  76.  
  77. 		System.out.println("Zig Zag Traversal is :");
  78. 		obj.zigzagTraverse(root);
  79. 	}
  80. }
  81.  
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Zig Zag Traversal is :
1	
3	2	
4	5	6	7	
9	8	
10
https://ideone.com/oKz0t3
language:
Java (12.0.1)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!