typedef int trieValueT;
 
 typedef struct trieNodeTag {
     char key;
     int words;
     int prefix;
     trieValueT value;
     struct trieNodeTag *next, *children;
} trieNodeT;

typedef struct trieCDT {
    trieNodeT *root;
} trieCDT;

typedef struct trieCDT *trieADT;

// Functions
void trieCreate(trieCDT *trie);
void trieAdd(trieNodeT *trie, char *key, int value);
trieNodeT* addChild(char key);
int trieIsMember(trieCDT trie, char keys[]);
int totalStringsWithPrefix(trieCDT trie, char keys[]);
void trieDestroy(trieNodeT *root);
void test1();
void startTesting();
void startTestingFromFile(char** stdip_v);

  
  #include <stdio.h>
  #include <stdlib.h>
  #include "trie.h"
  
  // To enable debug messages uncomment #define
  #define TEST 1
  // To test trie by providing input from file, uncomment 'TESTFROMFILE'
  // Compile code and while executing provide file name at command line
 // For e.g. > ./a.out ipFile.txt
 //
 //#define TESTFROMFILE 1
 //
 // To enable debug messages uncomment 'DEBUG'
 //#define DEBUG 1
 
 #ifdef DEBUG
 #  define D(x) x
 #else
 #  define D(x)
 #endif
 
 int main(int argc, char* argv[])
 {
     #ifdef TEST
         startTesting();
     #endif
 
     #ifdef TESTFROMFILE
         startTestingFromFile(argv);
     #endif
 
     return 0;
 }
 
 // Create root node of trie
 void trieCreate(trieCDT *trie)
 {
     trie->root = (trieNodeT*)calloc(1,sizeof(trieNodeT));
 
     if (trie->root == NULL) {
     printf("Can not alloc memory\n");
     return;
     }
 
     trie->root->key = '\0';
     trie->root->value = -1;
     trie->root->next = NULL;
     trie->root->children = NULL;
 }
 
 // This is recursive function for adding node in trie
 // It covers 3 cases
 // Case 1: When only root node is present in a trie. In this
 //         case keep on adding node one level after another.
 //
 //         If input given is "Good" and if 'G' is not found then
 //         insert 'G' and return 'G' node from where next insertion
 //         has to be done as we have already found there is no
 //         other 'G' exist.
 //
 // Case 2: When matching key node is already found return the matching
 //         node and increment key
 //
 // Case 3: When key does not match to existing children i.e. for
 //         "abcd", "abef" and "abgh"
 //         .  ----> root
 //         |
 //         a
 //         |
 //         b
 //         |
 //         c ===> e ===> g        (LL, children of b)
 //         |      |      |
 //         d      f      h
 
 
 void trieAdd(trieNodeT* trie, char *key, int value) {
 
     // Get root of children
     if (key == NULL) {
     return;
     } else if (trie->children == NULL && trie->next == NULL) {
 
         // Case 1
     trieNodeT* child = addChild(*key);
     trie->children = child;
 
     if (*key == '\0') {
         child->value = value;
         child->words++;
         return;
     }
 
     return trieAdd(child, ++key, value);
     }
 
     trieNodeT* level = trie->children;
     trieNodeT* current;
    for (current = level; current != NULL; current = current->next) {

    // Case 2
    if (current->key == *key) {
        current->prefix++;

        if (*key == '\0') {
        current->words++;
        return;
        }
        return trieAdd(current, ++key, value);
    }

    // This is last element in LL and key is not found
    // For e.g. for "abc" and "abd", c and d should be
    // child of b.
    // Since, c != d, Append d to c in LL signifying they
    // are both child of 'b' and are on same level
    //
    // Case 3
    if (current->next == NULL) {
        //Add key
        trieNodeT* child = addChild(*key);
        current->next = child;

        if (*key == '\0') {
            child->words++;
        child->value = value;
        return;
        }

        return trieAdd(child, ++key, value);
    }
    }
}

trieNodeT* addChild(char key)
{
    trieNodeT* child = (trieNodeT*)calloc(1,sizeof(trieNodeT));

    if (child == NULL) {
    printf("Can not alloc memory\n");
    return NULL;
    }
    child->key = key;
    child->value = -1;
    child->next = NULL;
    child->children = NULL;
    child->prefix = 1;
    child->words = 0;

    return child;
}

int totalStringsWithPrefix(trieCDT trie, char keys[])
{
    trieNodeT *level = trie.root->children;

    while (keys != NULL) {
    trieNodeT *found = NULL;
    trieNodeT *current;

    for (current = level; current != NULL; current = current->next) {
        if (current->key == *keys) {
        found = current;
        break;
        }
    }

    if (found == NULL) {
        return 0;
    } else if (*(keys + 1)  == '\0') {
        return found->prefix;
    }
    level = found -> children;
    keys++;
    }

    return 0;
}

int trieIsMember(trieCDT trie, char keys[])
{
    trieNodeT *level = trie.root->children;

    while (keys != NULL) {
    trieNodeT *found = NULL;
    trieNodeT *current;

    for (current = level; current != NULL; current = current->next) {
        if (current->key == *keys) {
        found = current;
        break;
        }
    }

    if (found == NULL) {
        return 0;
    } else if (*keys == '\0') {
        return 1;
    }
    level = found -> children;
    keys++;
    }

    return 0;
}

void trieDestroy(trieNodeT * root)
{
    if (root->children == NULL && root->next == NULL) {
        D(printf("Destroying %d\n", root->value));
    free (root);
    return;
    }

    // If root have next and children free them first
    if (root->next != NULL) {
    trieDestroy(root->next);
    }

    if (root->children != NULL) {
    trieDestroy(root->children);
    }

#ifdef DEBUG
    if (root->key != '\0') {
    printf("Destroying %c\n", root->key);
    } else {
    printf("Destroying Root %d\n", root->value);
    }
#endif

    free (root);
}

void test1()
{
    char s[] = "ABCD";
    char s1[] = "ABCDE";
    int i = 0;
    trieCDT trie;
    trieCreate(&trie);
    trieAdd(trie.root, "ABCD", 20);
    trieAdd(trie.root, "ABCDE", 30);

    if (trieIsMember(trie, s)) {
    printf("Found member 'ABCD'\n");
    }

    i = totalStringsWithPrefix(trie, "ABC");
    printf("Total words with prefix 'ABC' %d\n", i);

    trieDestroy(trie.root);
}

void startTesting()
{
    test1();
}

void startTestingFromFile(char** stdip_v)
{
    FILE *fp = NULL;
    char key[50];
    trieCDT trie;
    int i = 0;

    fp = fopen(stdip_v[1], "r");
    if(fp == NULL) {
    fprintf(stderr, "Can not read file!!\n");
    return;
    }

    trieCreate(&trie);

    while(fscanf(fp, "%s", key) != EOF) {
    trieAdd(trie.root, key, i);
    i++;

    if(!trieIsMember(trie, key)) {
        printf("Key '%s' NOT found in trie\n", key);
    }
    }

    printf("Total words inserted in trie %d\n", i);

    i = totalStringsWithPrefix(trie, "Abe");

    printf("Total prefixs with 'Abe' %d\n", i);

    trieDestroy(trie.root);
}

 
 class Solution {
     public:
     Solution(){};
     ~Solution() {};
 
     int evalRPN(vector<string> &tokens) {
         int num = 0;
         vector<string>::const_iterator cii;

        for(int ii=0; ii < tokens.size(); ii++)
        {
        num = atoi(tokens.at(ii).c_str());
        if (!((tokens[ii] == "+") || (tokens[ii] == "-") ||
                (tokens[ii] == "*") || (tokens[ii] == "/"))) {
            mystack.push(num);
        } else {
            if (mystack.empty()) {
            return 0;
            }

            num = mystack.top();
            mystack.pop();

            if (mystack.empty()) {
            return 0;
            }

            if (tokens[ii] == "+") {
            num += mystack.top();
            } else if (tokens[ii] == "-") {
            num = mystack.top() - num;
            } else if (tokens[ii] == "*") {
            num *= mystack.top();
            } else if (tokens[ii] == "/") {
            if (num == 0)  {
                return 0;
            }
            num = mystack.top() / num;
            } else {
            return 0;
            }

            mystack.pop();
            mystack.push(num);
        }
        }

        return mystack.top();
    }

    std::stack<int> mystack;
};

  
  #include <stdio.h>
  #include <stdlib.h>
  
  int arrLen = 5;
  int maxdepth = 0;
  int mindepth = 10;
  int totalElem = 8;
  
 typedef struct BST {
     int data;
     struct BST *left;
     struct BST *right;
 } nodeBST;
 
 void balanceBST(int arr[]);
 nodeBST* addNode(int data);
 void addNodeToBST(nodeBST *root, nodeBST *node);
 void traverse(nodeBST *root);
 void maxDepth(nodeBST *root, int depth);
 void minDepth(nodeBST *root, int depth);
 
 int maxDepthWithoutGlobalVar(nodeBST *root, int depth, int maxDeep);
 int minDepthWithoutGlobalVar(nodeBST *root, int depth, int minDeep);
 
 int main()
 {
     int arr[10] = {5,3,7,10,6,12,2,1};
 
     (void)balanceBST(arr);
 
     return 0;
 }
 
 void balanceBST(int arr[])
 {
     nodeBST *node;
     nodeBST *root;
     int max = 0;
     int min = 100000;
 
     for (int i = 0; i < totalElem; i++) {
     node = addNode(arr[i]);
     if (node == NULL) {
         return;
     }
 
     if (i == 0) {
         root = node;
         continue;
     }
 
     addNodeToBST(root, node);
     }
 
     printf("Nodes created\n");
     traverse(root);
     maxDepth(root, 0);
     printf("\nMax Depth %d\n", maxdepth);
     minDepth(root, 0);
     printf("Min Depth %d\n\n", mindepth);
 
     max = maxDepthWithoutGlobalVar(root, 0, max);
     printf("Max Depth %d\n", max);
 
     min = minDepthWithoutGlobalVar(root, 0, min);
     printf("Min Depth %d\n", min);
 
     if ((max - min) > 1) {
     printf("Binary search tree is not Balanced\n");
     } else {
     printf("Binary search tree is Balanced\n");
     }
 }
 
 nodeBST* addNode(int data)
 {
     nodeBST *node = (nodeBST*)calloc(1, sizeof(nodeBST));
 
     if (node == NULL) {
     return NULL;
     }
 
     node->data = data;
     node->left = NULL;
     node->right = NULL;
 
     return node;
 }
 
 void addNodeToBST(nodeBST *root, nodeBST *node)
 {
     while(root != NULL) {
     if (node->data < root->data) {
         if (root->left != NULL) {
         root = root->left;
         } else {
         root->left = node;
         return;
        }
    } else {
        if (root->right != NULL) {
        root = root->right;
        } else {
        root->right = node;
        return;
        }
    }
    }

    return;
}

void traverse(nodeBST *root)
{
    if (root == NULL) {
    return;
    } else {
    traverse(root->left);
    printf("%d ", root->data);
    traverse(root->right);
    }

    return;
}

void maxDepth(nodeBST *root, int depth)
{
    if (root == NULL) {
    if (maxdepth < depth) {
        maxdepth = depth;
    }
    } else {
    maxDepth(root->left, (depth + 1));
    maxDepth(root->right, (depth + 1));
    }
}

void minDepth(nodeBST *root, int depth)
{
    if (root == NULL) {
    if (mindepth > depth) {
        mindepth = depth;
    }
    } else {
    minDepth(root->left, (depth + 1));
    minDepth(root->right, (depth + 1));
    }
}

int maxDepthWithoutGlobalVar(nodeBST *root, int depth, int maxDeep)
{
    if (root == NULL) {
    if (maxDeep <= depth) {
        maxDeep = depth;
    }
    return maxDeep;
    } else {
        maxDeep = maxDepthWithoutGlobalVar(root->left, (depth + 1), maxDeep);
    maxDeep = maxDepthWithoutGlobalVar(root->right, (depth + 1), maxDeep);
    }

    return maxDeep;
}

int minDepthWithoutGlobalVar(nodeBST *root, int depth, int minDeep)
{
    if (root == NULL) {
    if (minDeep >= depth) {
        minDeep = depth;
    }
    return minDeep;
    } else {
        minDeep = minDepthWithoutGlobalVar(root->left, (depth + 1), minDeep);
    minDeep = minDepthWithoutGlobalVar(root->right, (depth + 1), minDeep);
    }

    return minDeep;
}

 
 
 int temp[TREESIZE];
 
 void traverse(nodeBST *root)
 {
     static int n = 0;
 
     if (root == NULL) {
        return;
    } else {
        traverse(root->left);
        temp[n++] = root->data;
        traverse1(root->right);
    }

    return;
}

for (int i = 0; i < TREESIZE; i++) {
    if (temp[i] > temp [i + 1]) {
        return 0; // Binary tree is not BST
    }    
}
return 1;

 
 int isBSTUtil(nodeBST* node, int min, int max);
  
 /* Returns true if the given tree is a binary search tree 
  (efficient version). */
 int isBST(nodeBST* node) 
 { 
   return(isBSTUtil(node, INT_MIN, INT_MAX)); 
 } 
 
/* Returns true if the given tree is a BST and its 
   values are >= min and <= max. */
int isBSTUtil(nodeBST* node, int min, int max) 
{ 
  /* an empty tree is BST */
  if (node==NULL) 
     return 1;
       
  /* false if this node violates the min/max constraint */ 
  if (node->data < min || node->data > max) 
     return 0; 
 
  /* otherwise check the subtrees recursively, 
   tightening the min or max constraint */
  return
    isBSTUtil(node->left, min, (node->data - 1)) &&  // Allow only distinct values
    isBSTUtil(node->right, (node->data + 1), max);  // Allow only distinct values
} 

 
  // Recursive inorder traverse
  void traverse(nodeBST *root)
  {
      if (root == NULL) {
          return;
      } else {
          traverse(root->left);
          printf("%d ", root->data);
         traverse(root->right);
     }
 
     return;
 }

 
  // Iterative
  // 1) Create an empty stack S.
  // 2) Initialize current node as root
  // 3) Push the current node to S and set current = current->left until curt is NULL
  // 4) If current is NULL and stack is not empty then$
  //      a) Pop the top item from stack.
  //      b) Print the popped item, set current = current->right
  //      c) Go to step 3.
 // 5) If current is NULL and stack is empty then we are done.
 
 void iterativeInorder(nodeBST *root)
 {
     createStack();
 
     while(1) {
         if (root != NULL) {
             // Keep pushing in the stack
             push(root);
             root = root->left;
         } else {
             if (isStackEmpty()) {
                 break;
             }
 
             root = pop();
             printf("%d ", root->data);
 
             root = root->right;
         }
     }
 }

 
   void MorrisInorder(nodeBST *root) {
       nodeBST* current,*pre;
       current=root;
       while(current!=NULL) {
           if(current->left==NULL) {
               printf("%d ",current->data);
               current=current->right;
           }
          else {
              pre=current->left;
              while(pre->right != NULL && pre->right !=current)
                  pre=pre->right;
              if(pre->right==NULL) {
                  printf("Link %d, %d\n", pre->data, current->data);
                  pre->right=current;
                  current=current->left;
              }
              else {
                  pre->right=NULL;
                  printf("%d ",current->data);
                  current=current->right;
              }
          }
      }
  }