To find largest element smaller than K in a BST

Question

Given a binary search tree and an integer K, i would like to find the largest element less than K.

In the below tree,

for K = 13, result = 12
for K = 10, result = 8
for K = 1 (or) 2, result = -1

      10

  5       12

2   8   11  14

I tried the below logic. But is there any better way to do this ?

int findNum(node* node, int K)
{
        if(node == NULL)
        {
                return -1;
        }
        else if(K <= node->data)
        {
                return findNum(node->left,K);
        }
        else if(K > node->data)
        {
                int t = findNum(node->right,K);
                return t > node->data ? t : node->data;
        }

        return -1;
}

Answer 1

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;
}

Answer 2

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)
}