**ZigZag** is a tree traversal algorithm that traverses the nodes in each level from left to right and then from right to left.

Take a look at the tree below:

The zigzag traversal of this tree would be $4, 5, 2, 1, 3$. The first level, which is just the root node, needs to be traversed from *left to right*. The next level is then traversed from *right to left*, i.e., 5, then 2, and so on.

# Algorithm

Zigzag traversal can be implemented using *two stacks*, one stack for the current level (`curr`) and another for the next level (`next`).

- Keep track of the direction to traverse using the variable `isLtoR`. If `isLtoR` is *true*, then the current level needs to be traversed from left to right and vice versa.

- Push the root node into `curr` and set `isLtoR` to *false* for the next level.

- Pop a node from `curr` and store it in the variable `temp`. Deduce the direction from `isLtoR` and decide, depending on the direction, whether the left child or the right child is to be pushed into `next` first.

- Repeat the above step until `curr` is empty. When it is empty, swap the two stacks so that `next` becomes the emptied `curr` and `curr` becomes `next`.

- Repeat the steps above until `curr` is eventually empty.

# Code

The code tabs below implement the algorithm above:

#include <iostream> 
#include <stack> 
using namespace std; 

struct Node { 
	int data; 
	struct Node* left_node;
    struct Node* right_node; 
}; 

void ZigZag(struct Node* root) 
{ 
	
	if (root == 0) 
		return; 
 
  // 2 stacks
	stack<struct Node*> curr; 
	stack<struct Node*> next; 

	// push the root 
	curr.push(root); 

	// direction variable 
	bool isLtoR = true; 

	while (!curr.empty()) { 

		// pop from stack
		struct Node* temp = curr.top(); 
		curr.pop(); 

		if (temp != 0) { 

			// if temp exists, print temp 
			cout << temp->data << " "; 
 
			// pushing the nodes in next
			if (isLtoR == true) { 
				if (temp->left_node != 0) 
					next.push(temp->left_node); 
				if (temp->right_node != 0) 
					next.push(temp->right_node); 
			} 
			else { 
				if (temp->right_node != 0) 
					next.push(temp->right_node); 
				if (temp->left_node != 0) 
					next.push(temp->left_node); 
			} 
		} 

		if (curr.empty()) { 
			isLtoR = !isLtoR; 
      stack<struct Node*> temp_stack = next;
      next = curr;
      curr = temp_stack;
			 
		} 
	} 
} 

// function to add a node
struct Node* add_node(int data) 
{ 
	struct Node* node = new struct Node; 
	node->data = data; 
	node->left_node = node->right_node = 0; 
	return node; 
} 

int main() 
{ 

	struct Node* root = add_node(4); 
	root->left_node = add_node(2); 
	root->right_node = add_node(5); 
	root->left_node->left_node = add_node(1); 
	root->left_node->right_node = add_node(3); 
	cout << "ZigZag traversal: ";
  ZigZag(root); 

	return 0; 
} 

class Node: 
	 
	def __init__(self, data): 
		self.data = data 
		self.left_node = None
		self.right_node = None

def ZigZag(root): 
 
	if root is None: 
		return

	# 2 stacks
	curr = [] 
	next = [] 

	# push the root 
	curr.append(root) 

	#  direction variable 
	isLtoR = True

	while len(curr) != 0: 

		# pop from stack 
		temp = curr.pop(-1) 
		
		# if temp exists, print temp  
		print(temp.data) 

		# pushing the nodes in next
		if isLtoR == True: 
			if temp.left_node != None: 
				next.append(temp.left_node) 
			if temp.right_node != None: 
				next.append(temp.right_node) 
		else: 
			if temp.right_node != None: 
				next.append(temp.right_node)  
			if temp.left_node != None: 
				next.append(temp.left_node) 

		# check if curr is empty
		if len(curr) == 0: 
			isLtoR = not isLtoR
			curr, next = next, curr 


root = Node(4) 
root.left_node = Node(2) 
root.right_node = Node(5) 
root.left_node.left_node = Node(1) 
root.left_node.right_node = Node(3) 
print("ZigZag traversal:") 
ZigZag(root)

Python

What is zigzag tree traversal?

ZigZag tree traversal switches direction level by level, using two stacks to alternate traversals.