CareerCup

Node * getNextLeastNode( Node *root, int item)
{
	Node *cur = NULL, *prev = NULL;
	if( root == NULL)
		return NULL;
	cur = DFSBST(root, item);
	if(cur != NULL)
		cur = cur ->left;
	while ( cur != NULL )
	{
		prev = cur;
		cur = cur->right;
	}
	return prev;

}
Node* DFSBST( Node *root, int item)
{
	
	Stack stack;
	Push( &stack, root);
	while( Pop( &stack, &root) )
	{
		if( root -> data == item )
			return root ;
		if (root -> right )
			Push( &stack, root ->right );
		if (root -> left )
			Push( &stack, root ->left );
	}
	return NULL;
}

For a given subtree, there are 3 cases:
(1)root is NULL, then no such node in this subtree
(2)root->val < K, then the result might be in the root's right subtree or just root itself
(3)root->val >= K, then the result could only be in the root's left subtree
Following is C code:

TreeNode* findNextSmallerInBST(TreeNode* root, int K)
{
	if(root == NULL) return NULL;
	else if(root->val < K){
		TreeNode* t = findNextSmallerInBST(root->right, K);
		return t != NULL ? t : root;
	}
	else return findNextSmallerInBST(root->left, K);
}

Trace from the left child starting from the root until there's no left child. This node the minimum of the tree. If the node has right child, the second minimum is the minimum of the left child sub tree. Otherwise, he second minimum is its parent.