do morris traversal until you find k. but that may modify the tree if you break as you find k.
On Sat, Jul 30, 2011 at 9:14 AM, ankit sambyal <[email protected]>wrote: > Here the required program : > > void findkthSmallest(Node *root,int k) > { > Node *stack[100]; > int top=-1,count=0; > Node *temp; > stack[++top]=root; > > /*First we will find the minimum node*/ > temp=root; > while(temp->left != NULL) > { > stack[++top]=temp->left; > temp->left=NULL; //Make it NULL so that we do not traverse it > again > temp=temp->left; > } > //Now top of the stack contains the minimum node. > //Now we will do inorder traversal > while(top!=-1) > { > temp=stack[top]; > count++; //Increment the count for every eleemnt > traversed > if(count==k) //If count reaches k, we have kth smallest > element as the top of the stack > return stack[top]->value; > else if(temp->left!=NULL) > { > stack[++top]=temp->left; > temp->left=NULL; //Make it NULL so that we do not traverse > it again > count++; > } > else if(temp->right!=NULL) > { > stack[++top]=temp->right; > temp->right=NULL; //Make it NULL so that we do not > traverse it again > count++; > } > else > top--; > > } > } > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Varun Pahwa B.Tech (IT) 7th Sem. Indian Institute of Information Technology Allahabad. Ph : 09793899112 Official Email :: [email protected] Another Email :: [email protected] People who fail to plan are those who plan to fail. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
