To find largest element smaller than K in a BST

I think the idea here is to record the last node after which you move to the right subtree. Therefore, the code will be (has been updated)

int findNum (Node *node, int K)
{
    Node* last_right_move = NULL;

    while (node)
    {
        if (K<=node->data)
            node = node->left;
        else
        {
            last_right_move = node;
            node = node->right;
        }
    }

    if (last_right_move)
        return last_right_move->data;
    else
        return NOT_FOUND;  // defined previously. (-1 may conflict with negative number)
}

I suggest that you walk through the code in your local implementation of set::upper_bound for guidance. This is not the solution to your exact problem, but very close.

In general in real life, most of these problems do not need to be solved in your own code. STL can do many common tasks for you. It's useful to know how to solve them of course, hence the test.

I believe in using standard library facilities. Thus, my solution uses std::set. :-)

int largest_num_smaller_than(std::set<int> const& set, int num)
{
    std::set<int>::const_iterator lb(set.lower_bound(num));
    return lb == set.begin() ? -1 : *--lb;
}

That's O(log n), which is the minimum. However, you can improve the efficiency (which seems to be the main thing these interviewers care about) and eliminate the possibility of stack overflow (tada!) by eliminating tail recursion, turning this into a loop. Also, your code doesn't work if the tree contains negative numbers ... if you mean non-negative integers, you should say so, but if the interviewer just said "integers" then you need slightly different code and a different API. (You could keep the same function signature but return K instead of -1 upon failure.)

BTW, since this is an interview question, implementing it by calling a library function would tell most interviewers that you are a smartass or are missing the point or don't know how to solve it. Don't mess around with that sort of thing, just get to working on what you know the interviewer wants.

Here is an implementation:

// Return the greatest int < K in tree, or K if none.
int findNum (Node* tree, int K)
{
    int val = K;

    while( tree )
        if( tree->data >= K )
            tree = tree->left;
        else{
            val = tree->data; 
            tree = tree->right;
        }

    return val;
}