# 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:**