Given a binary tree, print it's elements in **Zigzag Order**, see the example below for illustration:

##### Example 1: Print a Binary Tree in Zigzag Order

Input:

**Output: **1, 3, 2, 4, 5, 6, 7, 9, 8

## Solutions

### Method 1: Using two Stacks

Observing closely we can find that, to print a binary tree in "ZigZag" order we need to print "even levels" of the tree from "left-to-right" and "odd levels" from "right to left".

We can achieve this using **"two stacks"**, one to hold even level nodes and other to hold odd level nodes.

Add root to even-stack, keep the loop going until both stacks are not empty.

The idea is to pop elements from one stack one-by-one and print, also store their children in other stack - "right than left" for odd-stack and "left than right" for even-stack.

if(root==null) return; evenLevel -> empty stack evenLevel.add(root) oddLevel -> empty stack while(not empty evenLevel || not empty oddLevel) while(not empty evenLevel) node -> evenLevel.pop() print(node) if (node.left != null) oddLevel.add(node.left) if (node.right != null) oddLevel.add(node.right) while (not empty oddLevel) node = oddLevel.pop() print(node.data + ", ") if (node.right != null) evenLevel.add(node.right) if (node.left != null) evenLevel.add(node.left)

##### Complexity

**O(n)**and space complexity is

**O(n+n)**due to auxiliary Stacks.

### Method 2: Using Queue & List

Observing closely we can find that, to print a binary tree in **"ZigZag"** order we need to print "even levels" of the tree from "left-to-rigt" and "odd levels" from "right to left".

We can achieve this with the help of a **"temporary list"** while traversing the tree level-by-level using **Queue**.

The "tmp list" will be used to "store, reverse (if needed) and print" nodes of one level at a time, the remaining level order traversal algorithm using queue has no change.

The idea is to "add and print" nodes for even levels while "add, reverse list and print" nodes for odd levels.

if (root == null) return q -> empty queue q.add(root) evenLevel -> true while (!q.isEmpty()) int size = q.size(); nodesFromOneLevel -> empty list for (int i = 0; i < size; i++) n -> q.poll() nodesFromOneLevel.add(n); if (n.left != null) q.add(n.left) if (n.right != null) q.add(n.right) if (evenLevel) evenLevel -> false else reverse(nodesFromOneLevel) evenLevel = true forEach(i->nodesFromOneLevel) print(i.data)

##### Complexity

The time complexity of this solution is **O(n)** and space complexity is **O(2n) or O(n)** due to auxiliary Queue & List.