ZigZag Tree Traversal (Using queue) in C++

In this tutorial, we are going to learn about ZigZag Tree Traversal in C++. Firstly we are going to have an Introduction to the problem. Secondly, we will check the various solutions to the problem.

Introduction to ZigZag Tree Traversal

The tree is a data structure which consists of nodes and edges. Nodes are the data storing units. Edges are used to connect various nodes with each other. In this problem, we are going to use a binary tree. A binary tree is a special kind of tree, in a binary tree each parent can have at most two children.  Traversing a tree means visiting each node of the tree only once and to reach each and every one node.

There are many types of traversing simpler ones are :

  1. Preorder traversal: Firstly the parent is visited then the left child is visited and then the right child.
  2. Postorder traversal: Firstly the left child has visited then the right child and Finally the parent visits.
  3. Inorder traversal: Parent is visited first then the left and right child of the parent is visited.

In this tutorial, we are going to traverse the tree in a zigzag style. In zigzag style, we visit the nodes in a zigzag fashion.

To solve this problem we have to use a queue to traverse in that way.

                     1
                    / \
                   2   3     sequence of visiting : 1 3 4 5 6
                  / \   \
                 4   5   6

C++ Program: ZigZag Tree Traversal using queue

Here is the C++ code to perform ZigZag tree traversal.

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

struct Node { 
    int data; 
    struct Node *left, *right; 
}; 

void zizagtraversal(struct Node* root) 
{ 
 
    if (!root) 
        return; 
  
    stack<struct Node*> currentlevel; 
    stack<struct Node*> nextlevel; 
  
    currentlevel.push(root); 
  
    bool lefttoright = true; 
    while (!currentlevel.empty()) { 
  
        struct Node* temp = currentlevel.top(); 
        currentlevel.pop(); 
  
        if (temp) { 
  
            cout << temp->data << " "; 

            if (lefttoright) { 
                if (temp->left) 
                    nextlevel.push(temp->left); 
                if (temp->right) 
                    nextlevel.push(temp->right); 
            } 
            else { 
                if (temp->right) 
                    nextlevel.push(temp->right); 
                if (temp->left) 
                    nextlevel.push(temp->left); 
            } 
        } 
  
        if (currentlevel.empty()) { 
            lefttoright = !lefttoright; 
            swap(currentlevel, nextlevel); 
        } 
    } 
} 
  
struct Node* newNode(int data) 
{ 
    struct Node* node = new struct Node; 
    node->data = data; 
    node->left = node->right = NULL; 
    return (node); 
} 

int main() 
{ 
    struct Node* root = newNode(1); 
    root->left = newNode(2); 
    root->right = newNode(3); 
    root->left->left = newNode(7); 
    root->left->right = newNode(6); 
    root->right->left = newNode(5); 
    root->right->right = newNode(4); 
    cout << "ZigZag Order traversal of binary tree is \n"; 
  
    zizagtraversal(root); 
  
    return 0; 
}

Input and Output:

ZigZag Order traversal of binary tree is
1 3 2 7 6 5 4

Conclusion

This was the tutorial on the topic of ZigZag Tree Traversal. The concept of queue and tree traversal is covered in this tutorial. Using this method many tree traversal problems can be solved.

Also Checkout:

Finding most occurred element in an array in C++
Find the parent of a node in binary tree in Python
Morris Inorder Tree Traversal in C++

Leave a Reply

Your email address will not be published. Required fields are marked *