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.
