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;
}

Find the permutation and combination for a given string

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define ERRNUM -1
#define SUCCESS 0

#define TRUE 1
#define FALSE 0

#define TOTAL_ALPHA 26

/* Function   : permutations
 * Args       : str [IN]
 *              index [IN]
 *              result [IN/OUT]
 * Description: Function will print all the permutations and combinations of a given string 
 *              without repeated patterns. PnC(ABC) = { A+PnC(BC), B+PnC(CA), C+PnC(AB) } 
 * Note       : This "without repeated patterns" will not work for non-alpha characters [TBD]. 
 */
int permutations (char *str, int index, char *result)
{
  char *temp = NULL;           // To store the given string for processing
  int len = strlen (str);      // Length of the given string
  int count = 0;               // Counter variable used in the loop
  int j = 0;                   // Temporary variable
  char found[52] = {0};        // To check the variable to check the duplicate characters to avoid duplicate patterns

  /* Allocate memory for the temp variable to store the given string for processing.
   * So that the given string will not change. 
   */
  temp = (char *) calloc (len+1, sizeof (char));
  if (NULL == temp)
  {
    fprintf (stderr, "Memory allocation failed.\n");
    return ERRNUM;
  }

  /* Copy the given string into the temporary variable */
  strcpy (temp, str);

  /* Traverse through the string and find the permutations and combinations of the substring 
   * PnC(ABC) = { A+PnC(BC), B+PnC(CA), C+PnC(AB) } 
   */
  for (count=0; count < len; count++)
  {
    char ch = 0;
    
    *(result + index) = *temp;
    if (1 == len)
    {
      /* We can store in an array of string or a stack */
      printf ("%s\n", result);
    }
    else
    {
      if (isupper (*temp))
      {
        
        if (FALSE == found [TOTAL_ALPHA + (*temp) - 'A'])
        {
          found [TOTAL_ALPHA + (*temp) - 'A'] = TRUE;
        }
        else
        {
          /* Its a duplicate character */
          goto NEXT;
        }
      }
      else if (islower (*temp))
      {
        if (FALSE == found [(*temp) - 'a'])
        {
          found [(*temp) - 'a'] = TRUE;
        }
        else
        {
          /* Its a duplicate character */
          goto NEXT;
        }
      }
      
      /* We can store in an array of string or a stack */
      for (j=0; j<=index; j++)
      {
        printf ("%c", *(result+j));
      }
      printf ("\n");

      /* Find the permutations and combinations for the substring too */
      if (ERRNUM == permutations (temp+1, index+1, result))
      {
        return ERRNUM;
      }

    NEXT:
      ch = *temp;
      memcpy (temp, temp+1, len-1);
      temp[len-1] = ch;
    }
  }

  /* Free the allocated memory for the temporary variable */
  free (temp);

  return SUCCESS;
}

int main (int argc, char *argv[])
{
  char *result = NULL;        // Variable to store the result for printing 
  int retVal = SUCCESS;       // Variable to stroe the return value

  // No code to check/validate the input [TBD].

  if (NULL == result)
  {
    result = (char *) calloc (strlen (argv[1])+1, sizeof (char));
    if (NULL == result)
    {
      fprintf (stderr, "Memory allocation failed.\n");
      return ERRNUM;
    }
  }

  retVal = permutations (argv[1], 0, result);
  
  free (result);
    
  return retVal;
}

The results:

prompt$ ./permutationsNconbination ABC

A

AB

ABC

AC

ACB

B

BC

BCA

BA

BAC

C

CA

CAB

CB

CBA

prompt$ ./permutationsNconbination AAB

A

AA

AAB

AB

ABA

B

BA

BAA

prompt$ ./permutationsNconbination AAA

A

AA

AAA

prompt$