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 <ankitsamb...@gmail.com>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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> 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 :: rit2008...@iiita.ac.in
Another Email :: varunpahwa.ii...@gmail.com
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
