Write a function which does zig-zag traverse of binary tree and prints out nodes.

All the header files which are needed

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdexcept>
    

Brings all the named entities from std namespace into current declarative region

using namespace std;
    

This is the node structure we use to store the values and form the binary tree. For the simplicity, we use int data type to store the node data.

struct node {
  int val;
  struct node *left;
  struct node *right;
};

    

It prints the vector contents for debug purpose.

void printVector(vector<node *> list)
{
  for (vector<node *>::const_iterator i = list.begin(); i != list.end(); ++i)
  {
    if (NULL != *i)
      cout << "[" << (*i)->val << "] -> ";
    else
      cout << "[EMPTY] -> ";
  }
  cout << "NULL" << endl;
}

    

The input vector has all the nodes of a certain level (or depth) in the given tree, stored from left to right. This function is capable of printing either in the same order as the vector is created or in reverse order.

void printLevels(vector<node *>& level, int count, int forward)
{
  
  if (1 == forward) { // Print vector as it is
    for(vector<node *>::iterator it = level.begin(); it != level.end(); ++it) {
      if (*it)
        cout << (*it)->val << " ";
      else
        cout << "- "; // Empty Node
    }
  } else { // Print vector in reverse order
    for(vector<node *>::reverse_iterator it = level.rbegin(); it != level.rend(); ++it) {
      if (*it)
        cout << (*it)->val << " ";
      else
        cout << "- "; // Empty Node
    }
  }
  cout << endl;
}
    

The main function to trave level by level.

void traverse(node *binaryTree, bool ziczac)
{
  string zz = ziczac? "True":"False";
  cout << "ZicZac: [" << zz << "]" << endl;
  
  int count = 1;             // Initial count for the ROOT node (Level 1)
  int countNext = 0;         // Node count in the Next Level
  int forward = 1;           // Decides how to print the list
  vector<node *> nodeList;   // Store nodes level-by-level
  node *tmp = NULL;          // Store the node pointer temporarily 

  // Push the ROOT
  nodeList.push_back(binaryTree);
  
  while (0 != count) {
    // Print the nodes from the current level
    printLevels(nodeList, count, forward);
    
    // Iterate the nodes from current level and get the nodes from
    // the next level
    countNext = 0;
    for (int i=0; i<count;){
      tmp = nodeList.front();

      // Remove the node which is getting processed
      nodeList.erase(nodeList.begin());

      // Node is NULL. Don't count the NULL nodes
      if (NULL == tmp) {
        nodeList.push_back(NULL);
        nodeList.push_back(NULL);
      } else {
        i++;
      
        // Check the left child node
        if (tmp->left) {
          countNext++;
          
          // Push it to the list
          nodeList.push_back(tmp->left);
        } else {
          nodeList.push_back(NULL);
        }
        
        // Check the right child node
        if (tmp->right) {
          countNext++;
          
          // Push it to the list
          nodeList.push_back(tmp->right);
        } else {
          nodeList.push_back(NULL);
        }
      }
    }

    // update the current with the level count from the next level
    count = countNext;
    
    if (true == ziczac) {
      // Toggle the way the level is getting printed
      forward = (forward ^ 0x1) & 0x1;
    }
  }
}
    

Read the file with the following format,
('|' is the delimitor)
   1
   2|3
   4|5| |7
   8|9|0|1| | |2|3

and create the binary tree

node *createBinaryTreeFromFile(string filename)
{
  node *binaryTree = NULL;
  vector<node *> nodeList;
  vector<node *> childNodeList;
  vector<string> stringList;
  string line;
  
  try {

    // Open the given file
    ifstream inFile (filename);

    while ( getline (inFile, line) )
    {
      // First Line => ROOT node
      if (NULL == binaryTree) {
        binaryTree = new node;
        binaryTree->val = stoi(line);
        binaryTree->right = NULL;
        binaryTree->left = NULL;
        nodeList.push_back(binaryTree);
      } else {
        stringList.clear();
        string::size_type prev_pos = 0, pos = 0;
        // Split the line with '|' delimitor 
        while( (pos = line.find('|', pos)) != string::npos )
        {
          std::string substring( line.substr(prev_pos, pos-prev_pos) );
          stringList.push_back(substring);
          prev_pos = ++pos;
        }
        string substring( line.substr(prev_pos, pos-prev_pos) ); // Last word
        stringList.push_back(substring);

        // Create the binary tree here (level by level)
        vector<string>::iterator itStringList = stringList.begin();
        while (!nodeList.empty()) {
          
          if (itStringList >= stringList.end())
            break;

          if (NULL == *(nodeList.begin())) {
            itStringList = itStringList + 2;
          } else {
            // Left Node
            try{
              int val = stoi(*itStringList);
              node *tmp = new node;
              tmp->val = val;
              tmp->left = NULL;
              tmp->right = NULL;
              (*(nodeList.begin()))->left = tmp;
              itStringList++;
              nodeList.push_back(tmp);
            } catch (const invalid_argument& ia) {
              cerr << "Invalid argument: " << ia.what() << '\n';
              nodeList.push_back(NULL);
              itStringList++;
            }

            // Right Node
            try{
              int val = stoi(*itStringList);
              node *tmp = new node;
              tmp->val = val;
              tmp->left = NULL;
              tmp->right = NULL;
              (*(nodeList.begin()))->right = tmp;
              itStringList++;
              nodeList.push_back(tmp);
            } catch (const invalid_argument& ia) {
              cerr << "Invalid argument: " << ia.what() << '\n';
              nodeList.push_back(NULL);
              itStringList++;
            }
          }
          
          // Remove the node which is getting processed
          nodeList.erase(nodeList.begin());
        }
      }
    }
    inFile.close();
  } catch (ifstream::failure e) {
    cerr << e.what() << endl;
  }

  // Print the tree
  traverse(binaryTree, false);
  
  return binaryTree;
}
    

Everything starts from here,

int main(int argc, char** argv)
{
  node *binaryTree = createBinaryTreeFromFile(argv[1]);
  traverse(binaryTree, true);
  return 0;
}