Level Order zigzag

#1

import java.util.*;
public class Main {

static Scanner scn = new Scanner(System.in);

public static void main(String[] args) {
	Main m = new Main();
	BinaryTree bt = m.new BinaryTree();
	bt.levelOrderZZ();
}

private class BinaryTree {
	private class Node {
		int data;
		Node left;
		Node right;
	}

	private Node root;
	private int size;

	public BinaryTree() {
		this.root = this.takeInput(null, false);
	}

	public Node takeInput(Node parent, boolean ilc) {

		int cdata = scn.nextInt();
		Node child = new Node();
		child.data = cdata;
		this.size++;

		// left
		boolean hlc = scn.nextBoolean();

		if (hlc) {
			child.left = this.takeInput(child, true);
		}

		// right
		boolean hrc = scn.nextBoolean();

		if (hrc) {
			child.right = this.takeInput(child, false);
		}

		// return
		return child;
	}

	public void levelOrderZZ() {
		levelOrderZZ(this.root);
	}

	private void levelOrderZZ(Node node){
		Stack<Node> s1 = new Stack<>();
		Stack<Node> s2 = new Stack<>();
		s1.push(node);
		while(!s1.isEmpty() || !s2.isEmpty()){
			while(!s1.isEmpty()){
				Node temp = s1.pop();
				System.out.print(temp.data+" ");

				if(temp.left != null){
					s2.push(temp.left);
				}

				if(temp.right != null){
					s2.push(temp.right);
				}
			}
			
			
				while(!s2.isEmpty()){
					Node temp = s2.pop();
					System.out.print(temp.data+" ");

					if(temp.right != null){
						s1.push(temp.right);
					}

					if(temp.right != null){
						s1.push(temp.left);
					}
				}
				
			
		}
	}

}

}

//sir Iā€™m not able to pass all test cases can you pls tell what is wrong

#2

@Siddharth_sharma1808,

https://ide.codingblocks.com/s/222639 Corrected code.

We will be using 2 stacks to solve this problem. One for the current layer and other one for the next layer. Also keep a flag which indicates the direction of traversal on any level.

You need to pop out the elements from current layer stack and depending upon the value of flag push the child of current element in next layer stack. You should maintain the output sequence in the process as well. Remember to swap the stacks before next iteration.

#3

sir why we are using count variable?

#4

@Siddharth_sharma1808,
We use count to maintain direction of traversal on a level.

Print the zig zag order i.e print level 1 from left to right, level 2 from right to left and so on. This means odd levels should get printed from left to right and even levels should be printed from right to left.

As given in the question. We keep count to check whether we should go from left to right or right to left