Code for the spiral model import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.*; //class representing Structure of treeNode in the binary tree class treeNode { int data; treeNode left; treeNode right; treeNode(int value) { data = value; left = null; right = null; } } class Source { static treeNode rootNode; void printSpiral(treeNode rootNode) { if (rootNode == null) return; // NULL check /*Create two stacks named "left2Right" used for printing the levels from left to right and "right2Lef" used for printing the levels from right to left.*/ Stack left2Right = new Stack(); Stack right2Left = new Stack(); // Push root node to the stack right2Left.push(rootNode); // printing the spiral order traversal of the tree while (!right2Left.empty() || !left2Right.empty()) { // print all the nodes in the level from left to right while (!right2Left.empty()) { treeNode tempNode = right2Left.peek(); right2Left.pop(); System.out.print(tempNode.data + " "); // push the right child and then push the left child to the stack "left2Right" if (tempNode.right != null) left2Right.push(tempNode.right); if (tempNode.left != null) left2Right.push(tempNode.left); } // Print all the nodes in the level from right to left while (!left2Right.empty()) { treeNode tempNode = left2Right.peek(); left2Right.pop(); System.out.print(tempNode.data + " "); // push the left child and then push the right child to the stack "right2Left" if (tempNode.left != null) right2Left.push(tempNode.left); if (tempNode.right != null) right2Left.push(tempNode.right); } } } public static void main(String[] args) { Source binaryTree = new Source(); //root node of the binary tree treeNode rootNode; Scanner in = new Scanner(System.in); //number of elements int n = in.nextInt(), element; //queue used to create a binary tree Queue q = new LinkedList(); // creating a new binary tree. rootNode = new treeNode(in.nextInt()); q.add(rootNode); treeNode cur = null; for (int i = 1; i < n; i++) { cur = q.remove(); //Note: if the element is -1 then the node is null element = in.nextInt(); if (element != -1) { cur.left = new treeNode(element); q.add(cur.left); } i++; //Note: if the element is -1 then the node is null element = in.nextInt(); if (element != -1) { cur.right = new treeNode(element); q.add(cur.right); } } //print the spiral order traversal of the tree binaryTree.printSpiral(rootNode); } }
In bfs it would not be zigzag. It would print nodes from left to right in all levels unlike this problem where you have to print left to right and right to left for alternating levels.
