Find common elements in given two Binary Search Trees

 /*  
  * Two BST are given find common elements in both  
  * Algo works like this:  
  * Iteratively traverse both the tree in inorder fashion  
  * If the first tree node is less than the second tree move the  
  * first tree forward else if the second tree node is less than the  
  * first tree move second tree forward. If equal move both tree forward  
  * Do this operation till either one of the tree is complete.  
  *  
  */  
   
 void CommonElementsInBST(TreeNode* root1, TreeNode* root2) {  
      Stack *stack1 = createStack();  
      Stack *stack2 = createStack();  
      int commonElementCount = 0;  
   
      do {  
           while (root1 != NULL ) {  
                push(stack1, root1);  
                root1 = root1->left;  
           }  
           while (root2 != NULL ) {  
                push(stack2, root2);  
                root2 = root2->left;  
           }  
   
           if (isEmpty(stack1) != 0 && isEmpty(stack2)) {  
                root1 = (TreeNode*)top(stack1);  
                root2 = (TreeNode*)top(stack2);  
                if (*((int*)root1->object) < *((int*)root2->object)) {  
                     pop(stack1);  
                     root1 = root1->right;  
                } else if (*((int*)root1->object) > *((int*)root2->object)) {  
                     pop(stack2);  
                     root2 = root2->right;  
                } else {  
                     pop(stack1);  
                     pop(stack2);  
                     printf("%d ", *((int*) root1->object));  
                     root1 = root1->right;  
                     root2 = root2->right;  
                     commonElementCount++;  
                }  
           }  
      } while (((isEmpty(stack1) != 0) || root1 != NULL) && ((isEmpty(stack2) != 0) || root1 != NULL));  
      printf("Number of common elements are : %d", commonElementCount);  
 }  
   

Stack Operations

Stack create, push, pop, empty operations

 typedef struct _stack {
 int top;
 void* array[20];
} Stack;

Stack* createStack()  
 {  
   Stack *stack = malloc(sizeof(Stack));  
   memset(stack, 0, sizeof(Stack));  
   return stack;  
 }  
   
 void push(Stack* stack, void* elem)  
 {  
   stack->array[stack->top] = elem;  
   stack->top += 1;  
 }  
   
 void* pop(Stack* stack)  
 {  
   void* elem = stack->array[stack->top-1];  
   stack->top -= 1;  
   return elem;  
 }  

 void* top(Stack* stack)
 {
   if (stack->top == 0)
     return NULL;

   return stack->array[stack->top-1];
 }
   
 int isEmpty(Stack* stack)  
 {  
   return stack->top;  
 }  

Inorder Traversal of binary tree

Inorder traversal of binary tree - Recursive

  
typedef struct _binaryTreeNode
{
  struct _binaryTreeNode *left;
  struct _binaryTreeNode *right;
  void* object;
} TreeNode;

void inOrderTraversalRecursive(TreeNode* root) {  
   if (root == NULL )  
     return;  
   inOrderTraversalRecursive(root->left);  
   printf("%d ", *(int *) root->object);  
   inOrderTraversalRecursive(root->right);  
 }  

Inorder traversal of binary tree - Iterative

 void inOrderTraversalIterative(TreeNode* root) {  
   if (root == NULL )  
     return;     
   Stack *tempStack = createStack();   
   do {  
     while (root != NULL ) {  
       push(tempStack, root);  
       root = root->left;  
     }  
   
     if (isEmpty(tempStack) != 0) {  
       root = pop(tempStack);  
       printf("%d ", *((int*) root->object));  
       root = root->right;  
     }  
   } while ((isEmpty(tempStack) != 0) || root != NULL );  
 }  

PS: Stack related functions are here.

Mirror a Binary Tree

Following algorithm would create a mirror of a Tree

 void mirror(TreeNode* root) { 
   if (root == NULL ) 
     return; 
  
   TreeNode* temp = root->left; 
   root->left = root->right; 
   root->right = temp; 
   mirror(root->left); 
   mirror(root->right); 
 } 

Removing consecutive Zeros

 
/*Remove all two consecutive zeros in the given string.

 Example: a3409jd00dk000d

 Output: a3409jddk000d

 Note: If there are less/more than two consecutive zeros, they should not be replaced.

 */



void remove2zeros(char *input) {
 char *temp = input;

 while (*temp != '\0') {
  if (*temp == '0' && *(temp - 1) != '0' && *(temp + 1) == '0'
    && *(temp + 2) != '0') {
   temp = temp + 2;
  } else {
   if (input != temp) {
    *input++ = *temp++;
   } else {
    temp++;
    input++;
   }
  }
 }
 *input = '\0';
}