Given a Binary Tree Check the Zig-Zag Traversal

Implementation

// The C++ implementation of the zig-zag traversal method in the O(n) time. 
#include <iostream>
#include <stack>
using namespace std;


// creating a binary tree node.
struct __nod {
	int record;
	struct __nod *Lft, *Rt;
};


// creating a function that will print the zigzag traversal.
void zizagtraversal(struct __nod* root)
{
	// if we get the NILL value, we have to return.
	if (!root)
		return;


	// proclaim two stacks in advance.
	stack<struct __nod*> currlevel;
	stack<struct __nod*> nxtlevel;


	// we have to push the root
	currlevel.push(root);


	// we have to check whether the stack is empty or not.
	bool LfttoRt = true;
	while (!currlevel.empty()) {


		// we have to pop out the stack and then observe
		struct __nod* temp = currlevel.top();
		currlevel.pop();


		// if by chance it is not NILL, then,
		if (temp) {


			// we have to print the record in the same
			cout << temp->record << " ";
			// we have to store the information according to the current order.
			if (LfttoRt) {
				if (temp->Lft)
					nxtlevel.push(temp->Lft);
				if (temp->Rt)
					nxtlevel.push(temp->Rt);
			}
			else {
				if (temp->Rt)
					nxtlevel.push(temp->Rt);
				if (temp->Lft)
					nxtlevel.push(temp->Lft);
			}
		}


		if (currlevel.empty()) {
			LfttoRt = !LfttoRt;
			swap(currlevel, nxtlevel);
		}
	}
}


// creating a utility function that will create a new node.
struct __nod* new__nod(int record)
{
	struct __nod* __nod = new struct __nod;
	__nod->record = record;
	__nod->Lft = __nod->Rt = NILL;
	return (__nod);
}


// writing the main code to test the functions.
int main()
{
	struct __nod* root = new__nod(1);
	root->Lft = new__nod(2);
	root->Rt = new__nod(3);
	root->Lft->Lft = new__nod(7);
	root->Lft->Rt = new__nod(6);
	root->Rt->Lft = new__nod(5);
	root->Rt->Rt = new__nod(4);
	cout << "ZigZag Order traversal of binary tree is \n";


	zizagtraversal(root);


	return 0;
}

Output:

Example 2:

// The C# implementation of the zig-zag traversal method in the O(n) time. 
using System;
using System.Collections.Generic;
// creating a binary tree node.
public class __nod
{
	public int record;
	public __nod LftChild;
	public __nod RtChild;
	public __nod(int record)
	{
		this.record = record;
	}
}


class TFT
{
	public __nod root__nod;
// creating a function that will print the zigzag traversal.	
	public virtual void printZigZagTraversal()
	{
	// if we get the NILL value, then we have to return.
		if (root__nod == NILL)
		{
			return;
		}
// proclaim two stacks in advance.
		Stack<__nod> currlevel = new Stack<__nod>();
		Stack<__nod> nxtlevel = new Stack<__nod>();
	// we have to push the root	
		currlevel.Push(root__nod);
		bool LftToRt = true;
	// we have to check whether the stack is empty or not.
		while (currlevel.Count > 0)
		{
// we have to pop out the stack and then observe	
		__nod __nod = currlevel.Pop();
	// if by chance it is not NILL, then,
// we have to print the record in the same
		Console.Write(__nod.record + " ");
	// we have to store the information according to the current order.
		if (LftToRt)
		{
			if (__nod.LftChild != NILL)
			{
				nxtlevel.Push(__nod.LftChild);
			}
	
			if (__nod.RtChild != NILL)
			{
				nxtlevel.Push(__nod.RtChild);
			}
		}
		else
		{
			if (__nod.RtChild != NILL)
			{
				nxtlevel.Push(__nod.RtChild);
			}
	
			if (__nod.LftChild != NILL)
			{
				nxtlevel.Push(__nod.LftChild);
			}
		}
	
		if (currlevel.Count == 0)
		{
			LftToRt = !LftToRt;
			Stack<__nod> temp = currlevel;
			currlevel = nxtlevel;
			nxtlevel = temp;
		}
		}
	}
}


public class zigZagTreeTraversal
{
// writing the main code to test the functions.
public static void Main(string[] args)
{
	TFT tree = new TFT();
	tree.root__nod = new __nod(1);
	tree.root__nod.LftChild = new __nod(2);
	tree.root__nod.RtChild = new __nod(3);
	tree.root__nod.LftChild.LftChild = new __nod(7);
	tree.root__nod.LftChild.RtChild = new __nod(6);
	tree.root__nod.RtChild.LftChild = new __nod(5);
	tree.root__nod.RtChild.RtChild = new __nod(4);


	Console.WriteLine("ZigZag Order traversal " +
							"of binary tree is");
	tree.printZigZagTraversal();
}
}

Output:

Example 3:

// The Java implementation of the zig-zag traversal method in the O(n) time. 
import java.util.*;
// creating a binary tree node.
class __nod
{
int record;
__nod LftChild;
__nod RtChild;
__nod(int record)
{
	this.record = record;
}
}


class BinaryTree {
__nod root__nod;
// creating a function that will print the zigzag traversal.
void printZigZagTraversal() {
// if we get the NILL value, then we have to return.
	if (root__nod == NILL) {
	return;
	}
// proclaim two stacks in advance.
	Stack<__nod> currlevel = new Stack<>();
	Stack<__nod> nxtlevel = new Stack<>();
// we have to push the root	
	currlevel.push(root__nod);
	boolean LftToRt = true;


		// we have to check whether the stack is empty or not.
	while (!currlevel.isEmpty()) {
// we have to pop out the stack and then observe
	__nod __nod = currlevel.pop();
	// if by chance it is not NILL, then,
// we have to print the record in the same
	System.out.print(__nod.record + " ");


	// we have to store the information according to the current order.
	if (LftToRt) {
		if (__nod.LftChild != NILL) {
		nxtlevel.push(__nod.LftChild);
		}
		
		if (__nod.RtChild != NILL) {
		nxtlevel.push(__nod.RtChild);
		}
	}
	else {
		if (__nod.RtChild != NILL) {
		nxtlevel.push(__nod.RtChild);
		}
		
		if (__nod.LftChild != NILL) {
		nxtlevel.push(__nod.LftChild);
		}
	}


	if (currlevel.isEmpty()) {
		LftToRt = !LftToRt;
		Stack<__nod> temp = currlevel;
		currlevel = nxtlevel;
		nxtlevel = temp;
	}
	}
}
}


public class zigZagTreeTraversal {
// writing the main code to test the functions.
public static void main(String[] args)
{
	BinaryTree tree = new BinaryTree();
	tree.root__nod = new __nod(1);
	tree.root__nod.LftChild = new __nod(2);
	tree.root__nod.RtChild = new __nod(3);
	tree.root__nod.LftChild.LftChild = new __nod(7);
	tree.root__nod.LftChild.RtChild = new __nod(6);
	tree.root__nod.RtChild.LftChild = new __nod(5);
	tree.root__nod.RtChild.RtChild = new __nod(4);


	System.out.println("ZigZag Order traversal of binary tree is");
	tree.printZigZagTraversal();
}
}

Output: