Level Order Traversal and printing in zigzag pattern java

	package bst;
	import java.util.ArrayList;
	import java.util.LinkedList;
	import java.util.List;
	import java.util.Queue;
	import java.util.Stack;
	public class Graph_Traverse {
	private static final TreeNode EMPTY = new TreeNode(-1);
	private TreeNode head;
	public Graph_Traverse() {
	this.head = createTree();
	}
	public static void main(String[] args) {
	Graph_Traverse graph_Traverse = new Graph_Traverse();
	graph_Traverse.PrintLevelOrder();
	}
	private TreeNode createTree() {
	TreeNode n1 = new TreeNode(1);
	TreeNode n2 = new TreeNode(2);
	TreeNode n3 = new TreeNode(3);
	TreeNode n4 = new TreeNode(4);
	TreeNode n5 = new TreeNode(5);
	TreeNode n6 = new TreeNode(6);
	TreeNode n7 = new TreeNode(7);
	TreeNode n8 = new TreeNode(8);
	TreeNode n9 = new TreeNode(9);
	n1.left = n2;
	n1.right = n3;
	n2.left = n4;
	n2.right = n5;
	n3.left = n6;
	n3.right = n7;
	n4.left = n8;
	n4.right = n9;
	return n1;
	}
	public void PrintLevelOrder() {
	boolean forward = true;
	Queue<TreeNode> q = new LinkedList<TreeNode>();
	Stack<TreeNode> s = new Stack<TreeNode>();
	q.add(this.head);
	q.add(EMPTY);
	while (!q.isEmpty()) {
	TreeNode g = q.remove();
	if (g.left != null) {
	q.add(g.left);
	}
	if (g.right != null) {
	q.add(g.right);
	}
	if (g.equals(EMPTY)) {
	if (!q.isEmpty()) {
	q.add(EMPTY);
	}
	forward = !forward;
	while (!s.isEmpty()) {
	System.out.print(s.pop().data + " ");
	}
	continue;
	}
	if (forward == true) {
	System.out.print(g.data + " ");
	} else {
	s.push(g);
	}
	}
	}
	}
	class TreeNode {
	int data;
	TreeNode left, right;
	TreeNode(int data) {
	this.data = data;
	left = null;
	right = null;
	}
	@Override
	public boolean equals(Object n) {
	return (this.data == ((TreeNode) n).data);
	}
	}

view raw Graph_Traverse.java hosted with ❤ by GitHub

	package bst;
	import java.util.LinkedList;
	import java.util.Queue;
	/**
	* Created by panded4
	*/
	public class LevelOrderTraversalBST {
	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);
	LevelOrderTraversalBST l = new LevelOrderTraversalBST();
	System.out.println("Breadth First Search : ");
	l.levelOrderQueue(root);
	}
	public void levelOrderQueue(Node root) {
	Queue<Node> q = new LinkedList<Node>();
	if (root == null)
	return;
	q.add(root);
	int count = 1;
	while (!q.isEmpty()) {
	Node n = (Node) q.remove();
	System.out.print(" " + n.data);
	count += 1;
	if (n.left != null)
	q.add(n.left);
	if (n.right != null)
	q.add(n.right);
	}
	}
	}
	class Node {
	int data;
	Node left;
	Node right;
	public Node(int data) {
	this.data = data;
	this.left = null;
	this.right = null;
	}
	}

view raw LevelOrderTraversalBST.java hosted with ❤ by GitHub