Change the structure of a Tree node to hold a pointer for the next in-order element (sucessor).

Idea is simple, based on Threaded Trees concept.
We need to modify Morris In-Order Traversal algorithm a little to convert the tree into a linked list, where each node's right pointer will point to its in-order successor.

There is no need to change the current tree node structure.

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

/*Tree to InOrder list conversion*/
struct node*  MorrisInOrderConversion(struct node* root){
 struct node *curr,*pre,*head=NULL;
 
 if(root==NULL){
  return NULL;
 }
 
 curr=root;
 
 while(curr!=NULL){
  if(curr->left==NULL){
   if(head==NULL){
    head=curr;
   }
   curr=curr->right;
  }else{
   pre=curr->left;
   
   while(pre->right!=NULL && pre->right!=curr){
    pre=pre->right;
   }
   
   if(pre->right==NULL){
    pre->right=curr;
    curr=curr->left;
   }else{
    struct node* next=curr->right;
    struct node* temp=curr->right;
    curr->right=NULL;
    while(next->left!=NULL){
     next=next->left;
    }
    curr->right=next;
    curr=temp;
   }
  }
 }
 
 return head; //Returns head of the converted list
}

/*Traverse the Converted list*/
void traverseList(struct node* head){
 while(head!=NULL){
  printf("%d ",head->data);
  head=head->right;
 }
}

And One more approach also exists for this, which involves creating a new list without changing current tree structure.

This can be written with Morris In-Order Tree traversal algorithm or Generic In-Order traversal algorithm.

Below is the code for generic traversal algorithm.

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

/*New Node structure defined*/
struct iNode{
 struct node* pNode;
 struct iNode* successor;
};

/*Tree to InOrder List - Start */
void insertINode(struct node* p){
 struct iNode *temp = (struct iNode*)malloc(sizeof(struct iNode));
 temp->pNode=p;
 temp->successor=NULL;
 
 if(iHead==NULL){
  iHead=temp;
 }else{
  iList->successor=temp;
 }
 iList=temp; 
};

void inOrderList(struct node* root){
 if(root!=NULL){
  inOrderList(root->left);
  insertINode(root);
  inOrderList(root->right);
 }
};

void traverseIList(){
 struct iNode *curr=iHead; 
 while(curr!=NULL){
  printf("%d ",curr->pNode->data);
  curr=curr->successor;
 }
}
/*Tree to InOrder List - End */

InOrder Traversal of Tree with out using Stack and Recursion

The idea is to create links to root from predecessor node in the left sub-tree for each node.
When traversal on the current node in done, move to the right child and make that node as current node and follow the same procedure.

1. Start from the root of the current tree, as current node.
2. If current node's left Child is NULL
        print the node data.
        make right of the current node as current.
    else
        If right child of the right most node of the left sub-tree is NULL
           make it as a link to current node.
           make left of the current node as current.
        else
           print the current node data.
           make right of the current node as current.

void MorrisInOrderTraversal(struct node* root){
 struct node *curr,*pre;
 if(root==NULL){
  return;
 }
 
 curr=root;
 
 while(curr!=NULL){
  if(curr->left==NULL){
   printf("%d ",curr->data);
   curr=curr->right;
  }else{
   pre=curr->left;
   
   while(pre->right!=NULL && pre->right!=curr){
    pre=pre->right;
   }
   
   if(pre->right==NULL){
    pre->right=curr;
    curr=curr->left;
   }else{
    pre->right=NULL;
    printf("%d ",curr->data);
    curr=curr->right;
   }
  }
 }
}

Max values of Sliding Window of K, in an Array of length N(>K)

Q: An array of size N is given. Array is sub divided into sub array of size K. Find maximum value of each sub array.

It is sliding window. Let array be “1 2 3 4 5 6” and k=2
then Sub arrays {1 2},{2 3},{3 4},{4 5},{5 6}.

For all these sub arrays, maximum of each needs to found.[Array is unordered.]

struct node{ 
 int data, index; 
 struct node next; 
 struct node *prev; 
}; 

struct DQueue{ 
 struct node *front; 
 struct node *rear; 
}; 

struct DQueue createDQ(){ 
 struct DQueue* newNode=(struct DQueue*)malloc(sizeof(struct DQueue)); 
 newNode->front=newNode->rear=NULL; 
} 

bool isDQEmpty(struct DQueue* DQ){ 
 return (DQ->front==NULL); 
} 

struct node* createNode(int data,int index){ 
 struct node* newDQNode=(struct node*)malloc(sizeof(struct node)); 
 newDQNode->data=data; 
 newDQNode->index=index; 
 return newDQNode; 
} 

void pushDQFront(struct DQueue* DQ,int data,int index){ 
 struct node* temp=createNode(data,index); 
 if(DQ->front==NULL && DQ->rear==NULL){ 
  DQ->front=DQ->rear=temp; 
 }else{ 
  temp->next=DQ->front; 
  DQ->front->prev=temp; 
  DQ->front=temp; 
 } 
} 

void pushDQBack(struct DQueue* DQ,int data,int index){ 
 struct node* temp=createNode(data,index); 
 if(DQ->front==NULL && DQ->rear==NULL){ 
  DQ->front=DQ->rear=temp; 
 }else{ 
  DQ->rear->next=temp; 
  temp->prev=DQ->rear; 
  DQ->rear=temp; 
 } 
} 

void popDQFront(struct DQueue* DQ){ 
 if(isDQEmpty(DQ)){ 
  return; 
 } 
 struct node* temp=DQ->front; 
 if(DQ->front==DQ->rear){ 
  DQ->front=DQ->rear=NULL; 
 }else{ 
  DQ->front->next->prev=NULL; 
  DQ->front=DQ->front->next; 
  temp->next=NULL; 
 } 
 free(temp); 
 temp=NULL; 
} 

void popDQBack(struct DQueue* DQ){ 
 if(isDQEmpty(DQ)){ 
  return; 
 } 
 struct node* temp=DQ->rear; 
 if(DQ->front==DQ->rear){ 
  DQ->front=DQ->rear=NULL; 
 }else{ 
  DQ->rear->prev->next=NULL; 
  DQ->rear=DQ->rear->prev; 
  temp->prev=NULL; 
 } 
 free(temp); 
 temp=NULL; 
} 

struct node* frontOfDQ(struct DQueue* DQ){ 
 if(isDQEmpty(DQ)){ 
  return NULL; 
 } 
 return DQ->front; 
} 

struct node* rearOfDQ(struct DQueue* DQ){ 
 if(isDQEmpty(DQ)){ 
  return NULL; 
 } 
 return DQ->rear; 
} 

void maxSlidingWindow(int a[],int n,int k){ 
 int i; 
 struct DQueue* DQ=createDQ(); 

 for(i=0;i<k;i++){ 
  while(!isDQEmpty(DQ) && a[i] >= rearOfDQ(DQ)->data){ 
   popDQBack(DQ); 
  } 
  pushDQBack(DQ,a[i],i); 
 } 
 printf("%d",frontOfDQ(DQ)->data); 

 for(;i<n;i++){ 
  while(!isDQEmpty(DQ) && frontOfDQ(DQ)->index <= i-k){ 
   popDQFront(DQ); 
  } 
  while(!isDQEmpty(DQ) && a[i] >= rearOfDQ(DQ)->data){ 
   popDQBack(DQ); 
  } 
  pushDQBack(DQ,a[i],i); 
  printf("%d",frontOfDQ(DQ)->data); 
 } 
} 

int main(){ 
 int a[]={3,5,2,8,2,3,7,9,2,2,44,66,2,23,4,54,2}; 
 int n=sizeof(a)/sizeof(a[0]); 
 int k=4; 
 maxSlidingWindow(a,n,k); 
 system("PAUSE"); 
}

Find two elements which will sum up to a given value, in a Sorted Array.

Given sorted integer array and a given value we have to find two elements which will sum up to a given value.

Since it is a sorted array our job is so easy.

For example, array a is having n element in sorted order
A[0]<A[1]<A[2]<........<A[n-1];

From this we can deduce that,
A[0]+A[1]<A[0]+A[2]<A[0]+A[3].......;
A[0]+A[n-1]<A[1]+A[n-1]<.....<A[n-2]+A[n-1];

Compare from the extreme summations with the given value and increase or decrease the indexes according to the comparison.

Int a[SIZE];
Int a[SIZE];
int n;

void findTwoElementsToN(int a[],int n){
 int i=0;
 int j=sizeof(a)/sizeof(int) -1;
 int sum=0;

 if(i<j){
  sum=a[i]+a[j];
  if(sum<n){
   i++;
  }else if(sum>n){
   j--;
  }else{
    printf(“%d and %d”,a[i],a[j]);
  }
 }
}

Least Common Ancestor of two nodes in a Given Unordered Tree.

There can be three possibilities for finding LCA is a tree.
1. Both nodes belong to left sub-tree.
2. Both nodes belong to right sub-tree.
3. One per each sub-tree.
 In fact 4th possibility is also there, i.e. nodes are not at all present in the tree.

In the first case, Current node can't be the LCA because an CA exist in the left sub-tree.
Similarly, in the second case, Current node can't be the LCA because an CA exist in the right sub-tree.
In the third case, Current node will be the LCA.

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

struct node* leastCommonAncestor(struct node* root,struct node* p,struct node* q){
 
 if(root==NULL){
  return NULL;  //If no root  leastCommonAncestor is NULL.
 }

 if(root==p || root==q){
  return root; // Check if the current root is equal to any of the desired node.
 }else{
  struct node* l=leastCommonAncestor(root->left, p, q); // Find LCA in left of the tree
  struct node* r=leastCommonAncestor(root->right, p, q); // Find LCA in right of the tree
  
  if(l!=NULL && r!=NULL){
   return root; 
  }else if(l!=NULL && r==NULL){
   return l;
  }else if(l==NULL && r!=NULL){
   return r;
  }else{
   return NULL;
  }
 } 
}

Binary Tree Related

Code for the following Questions can be found in below code.

Q: Given a node of Binary Tree . find all node's at distance k from it .
Q: Simple InOrder, PreOrder, PostOrder Traversals of the Tree.
Q: Given a node in the Tree. Find path from the root of tree to the node.
Q: Given a node in the Tree. Find the height of the node from the root.

/*
Written By BrOkEN@!

Q: Given a node of Binary Tree . find all node's at distance k from it .
Q: Simple InOrder,PreOrder,PostOrder Traversals of the Tree.
Q: Given a node in the Tree. Find path from the root of tree to the node.
Q: Given a node in the Tree. Find the height of the node from the root.

*/

#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<cstdio>
#include<cstdlib>
#include<cstddef>
#include<cstring>
#include<cctype>
#include<cmath>
#include<cassert>
#include<climits>

#define INFINITE 1000000

using namespace std;

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

struct trackNode{
 struct node* pNode;
 struct trackNode* parent;
};

struct trackNode *list=NULL,*head=NULL;

void insertTrackNode(struct node* p){
 struct trackNode *temp = (struct trackNode*)malloc(sizeof(struct trackNode));
 temp->pNode=p;
 
 if(list==NULL){
  head=temp;
 }else{
  list->parent=temp;
 }
 list=temp; 
};

/*Find path from root to Specific Node*/
bool trackPath(struct node *root, struct node *p){
 
 if(root==NULL){
  return false;
 }
 
 if(root==p){
  insertTrackNode(root);
  return true;
 }else{
  if(trackPath(root->left,p)||trackPath(root->right,p)){
   insertTrackNode(root);
   return true;
  }else{
   return false;
  }
 }
};

/*Constructing a tree and returning the root*/
struct node* buildTree(){
 struct node* n01=(struct node*) malloc(sizeof(struct node));n01->data=1;
 struct node* n02=(struct node*) malloc(sizeof(struct node));n02->data=2;
 struct node* n03=(struct node*) malloc(sizeof(struct node));n03->data=3;
 struct node* n04=(struct node*) malloc(sizeof(struct node));n04->data=4;
 struct node* n05=(struct node*) malloc(sizeof(struct node));n05->data=5;
 struct node* n06=(struct node*) malloc(sizeof(struct node));n06->data=6;
 struct node* n07=(struct node*) malloc(sizeof(struct node));n07->data=7;
 struct node* n08=(struct node*) malloc(sizeof(struct node));n08->data=8;
 struct node* n09=(struct node*) malloc(sizeof(struct node));n09->data=9;
 struct node* n10=(struct node*) malloc(sizeof(struct node));n10->data=10;
 struct node* n11=(struct node*) malloc(sizeof(struct node));n11->data=11;
 struct node* n12=(struct node*) malloc(sizeof(struct node));n12->data=12;
 struct node* n13=(struct node*) malloc(sizeof(struct node));n13->data=13;
 struct node* n14=(struct node*) malloc(sizeof(struct node));n14->data=14;
 struct node* n15=(struct node*) malloc(sizeof(struct node));n15->data=15;
 
 n08->left=n04;n08->right=n12;
 
 n04->left=n02;n04->right=n06;
 n02->left=n01;n02->right=n03;
 n06->left=n05;n06->right=n07;
 
 n12->left=n10;n12->right=n14;
 n10->left=n09;n10->right=n11;
 n14->left=n13;n14->right=n15;
 
 n01->left=n01->right=NULL;
 n03->left=n03->right=NULL;
 n05->left=n05->right=NULL;
 n07->left=n07->right=NULL;
 n09->left=n09->right=NULL;
 n11->left=n11->right=NULL;
 n13->left=n13->right=NULL;
 n15->left=n15->right=NULL;

 
 return n08;
};

/*InOrder Traversal of Tree with root Node*/
void inOrder(struct node* root){
 if(root!=NULL){
  inOrder(root->left);
  printf("%d ",root->data);
  inOrder(root->right);
 }
};

/*PreOrder Traversal of Tree with root Node*/
void preOrder(struct node* root){
 if(root!=NULL){
  printf("%d ",root->data);
  preOrder(root->left);
  preOrder(root->right);
 }
};

/*PostOrder Traversal of Tree with root Node*/
void postOrder(struct node* root){
 if(root!=NULL){
  postOrder(root->left);
  postOrder(root->right);
  printf("%d ",root->data);
 }
};


/*Find Nodes at distance K from the root(possibility to skip subtree is also provided.)*/
void findNodesAtDistanceK(struct node *root,int k,bool left,bool right){
 
 
 if(root!=NULL){
  if(k==0){
   printf("%d ",root->data);
   return;
  }
  
  if(left==true && right==false){
   findNodesAtDistanceK(root->left,k-1,true,true);
  }else if(left==false && right==true){
   findNodesAtDistanceK(root->right,k-1,true,true);
  }else{
   findNodesAtDistanceK(root->left,k-1,true,true);
   findNodesAtDistanceK(root->right,k-1,true,true);
  }
 }
}

/*Get Height of the node*/
int getHeight(struct node* root,struct node* p){
 
 if(root==NULL){
  return INFINITE;
 }
 
 if(root==p){
  return 0;
 }else{
  int l=1+getHeight(root->left,p);
  int r=1+getHeight(root->right,p);
  if(l>r){
   return r;
  }else{
   return l;
  }
 }
}


int main(){
 int k=3;//Distance
 struct node *root=NULL;
 root=buildTree();
 
 struct node* p=root->right->left->right; //get a random node from Tree

 if(trackPath(root,p)){
  int i=0;
  struct trackNode* prev=NULL;
  while(head!=NULL && i<=k){

   if(prev==NULL){
    findNodesAtDistanceK(head->pNode,k-i,true,true);
   }else{
    findNodesAtDistanceK(head->pNode,k-i,head->pNode->left!=prev->pNode,head->pNode->right!=prev->pNode);
   }
   
   prev=head;
   head=head->parent;
   i++;
  }
 }

 system("PAUSE");
}

Google Code Jam 2012 - Qualification Round

Compared to my performance in 2011 Code Jam, this year I just turned out to be a big disaster.
Yes, and I found that its very hard to make my rusted brain to make it work on these awesome set of problems. Thank God the qualification cut-off was too low...so that Idiots like me also get into to Round-1 :P :P.

Problem 1 - Speaking in Tongues
I guess most of the people would have cracked it very easily and it was the same for me. Not much to think about the solution. Its just a Character Mapping from the input set. You will be able to map all 26-character very easily.

import java.util.Arrays;
import java.util.Scanner;

public class Problem1 {
 public static void main(String args[]){
  Scanner in= new Scanner(System.in);
  String Normal="abcdefghijklmnopqrstuvwxyz ";
  String Google="yhesocvxduiglbkrztnwjpfmaq ";
  String fline=in.nextLine();
  Scanner in1= new Scanner(fline);
  int T = in1.nextInt();
  for(int l=0;l<T;l++){
   StringBuffer G=new StringBuffer(in.nextLine());
   System.out.print("Case #"+(l+1)+": ");
   for(int i=0;i<G.length();i++){
    System.out.print(Google.charAt(Normal.indexOf(G.charAt(i))));
   }
   System.out.println();
  }
 }
}

Problem 3: Recycled Numbers
I thought it was a easy problem and I did solved the small input set. But the real problem was Large Input set and I made a big blunder in the computation.
I gave generic solution but never thought that the code would ditch me in large number range.After all i'm a bad coder. :P :P
This is what i've written for the small input set. There are better algorithms than what i've written here.
I could've avoided below silly mistakes. Anyways it saved me :D.
Didn't give much attention trailing 0's.
Computations take much time for Input range is large. I should've been little smart using the HashSet etc to get rid of duplicates.
I should've make use of the boundary conditions effectively.

import java.util.Scanner;

public class Problem3 {
 public static void main(String args[]){
  Scanner in= new Scanner(System.in);
  Scanner rin= new Scanner(in.nextLine());
  int T = rin.nextInt();
  for(int l=0;l<T;l++){
   rin= new Scanner(in.nextLine());
   int lower = rin.nextInt();
   int upper = rin.nextInt();
   int count=0;
   while(lower<upper){
    for(int m=lower+1;m<=upper;m++){
     if(isRecycledPair(lower,m)){
      count++;
     }
    }
    lower++;
   }
   System.out.println("Case #"+(l+1)+": "+count);
  }
  
 }
 
 static String rightRotateString(String str){
  char strC[]=str.toCharArray();
  int i=0;
  char temp=strC[strC.length-1];
  for(i=strC.length-1;i>0;i--){
   strC[i]=strC[i-1];
  }
  strC[i]=temp;
  return (new String(strC));
 }
 
 static boolean isRecycledPair(int n,int m){
  String nS=Integer.toString(n);
  String mS=Integer.toString(m);
  if(nS.matches(mS))
   return true;
  for(int i=0;i<nS.length()-1;i++){
   nS=rightRotateString(nS);
   if(nS.matches(mS)){
    return true;
   }
  }
  return false;
 }
}

This is one of the work arounds for the same. The logic simple. Take a each number in the range. find all the rotations of that string :D . and the pair is definately a ReCycled pair for god sake :P :P. But you need to take care of the duplicates if there are any, so HashSet ;).

import java.util.HashSet;
import java.util.Scanner;

public class Problem3 {
 public static void main(String args[]){
  Scanner in= new Scanner(System.in);
  Scanner rin= new Scanner(in.nextLine());
  int T = rin.nextInt();
  for(int t=1;t<=T;t++){
   rin= new Scanner(in.nextLine());
   System.out.println("Case #"+t+": "+getNumberOfPairs(rin.nextInt(),rin.nextInt()));
  }
 }
 
 private static int getNumberOfPairs(int A,int B){
  int count=0;
  HashSet<Integer> s = new HashSet<Integer>();
  for (int n = A; n < B; n++) {
   String i=Integer.toString(n);
   s.clear();
   int t = i.length();
   while(i.charAt(t-1)=='0')
    t--;
   for(int j=1;j<t;j++){
    int m= Integer.parseInt(i.substring(j)+i.substring(0,j));
    if(n<m && m<=B){
     s.add(m);
    }
   }
   count+=s.size();
  }
  return count;
 }
}

Problem 2: Dancing with Googlers
This is one of the good problem. I guess, I was too lazy to think so I didn't try to solve this one in contest.
I missed one point while reading the problem, and I paid for that mistake in time :'(.

No triplet of scores contains scores that are more than 2 apart. - This one made my day like hell.

what are the possible sets.
Logic-1: If X is maximum then possible minimum will be X-2 in the triplet. Because possible triplets like this could be (X,X-2,X-2) or (X,X,X-2) or (X,X-1,X-2). Ofcourse they are surprising.
Logic-2: If X is maximum then possible minimum could be X-1 in the triplet.(Since Minimum X-1 is already ruled out in Logic-1). The possible triplets like this could be (X,X-1,X-1) or (X,X,X-1) - But these are not surprising Triplets
Logic-3: If X is maximum/minimum then possible triplet is (X,X,X) hehe Silly it not a Surprising Triplet.

So,
If a triplet is surprising then Maximum will be Average+ (1 or 2).
If a triplet is not surprising then Maximum will be Average+ (0 or 1).

If both are equal or more than P and maximum of surprising is equal or more than maximum of not surprising , then throw a count for it.
Simple it can be either surprising or not ....whats the big deal it has maximum than P in either case.
Save the urge to getting surprised for later, when you are sure that you will be more surprised with that triple.

import java.util.Scanner;

public class Problem2 {
 
 private static int isMaxSurprising(int sum){
  if(sum%3==0 && sum>0){
   return (sum/3)+1;
  }
  return (sum/3)+(sum%3);
 }
 
 private static int isNotMaxSurprising(int sum){
  if(sum%3==0 && sum>=0){
   return (sum/3);
  }
  return (sum/3)+1;
 }
 
 
 public static void main(String args[]) throws Exception{
  Scanner in= new Scanner(System.in);
  Scanner rIn= new Scanner(in.nextLine());
  
  int T=rIn.nextInt();
  
  for(int t=1;t<=T;t++){
   String nextLine=in.nextLine();
   rIn = new Scanner(nextLine);
   int N=rIn.nextInt();
   int S=rIn.nextInt();
   int p=rIn.nextInt();
   int count=0;
   for(int i=1;i<=N;i++){
    int sum=rIn.nextInt();
    int isMax=isMaxSurprising(sum);
    int isMaxNot=isNotMaxSurprising(sum);
    if(isMax >= isMaxNot && isMaxNot>=p){
     count++;
    }else if(S>0 && isMax >= isMaxNot && isMax >=p && isMaxNot <p){
     count++;
     S--;
    }
   }
   
   System.out.println("Case #"+t+": "+count);
  }
 }
}

Problem D. Hall of Mirrors
I'm still thinking about it.:P