Floor Value of an element in a Binary Search Tree

Question

So I was reading the book - Data Structures and Algorithms Made Easy by Narasimha Karumanchi and in that the floor Value of a bst snippet is given - Problem 61 in BST Chapter. The snippet confused me very much and now I just want to know how it is working : The snippet as Follows :

node* floorValue(node* root, node* prev ,int k)
{
    if(!root){
        return NULL;
    }

    if( !(floorValue(root->left , prev ,k))
    {
        return 0;
    }
    if(root->data == k)
    {
        return root;
    }
    if(root->data > k)
    {
        return prev;
    }
    prev = root;
    return floorValue(root->right , prev , k);
}

In this the node* prev which is initiated with NULL is storing the previous node and int k is the integer for which we are finding the floor value.

Can someone please help me in understanding its recursion. I am confused because :

1 . The code : if( !(floorValue(root->left , prev ,k)) { return 0; } will return 0 when the left most of the element of the tree is hit. But that will trigger all the recursive calls return 0.

2. Why it's returning 0 when we are returning the node* and not any int

Help will be really appreciated. I have solved this question but it was not using this method but a more straight forward one ( according to me ). I want to know what am I doing wrong or what I am missing in this code.

Input: The First input will be the number of nodes: The next n lines will be the nodes data. The first input after n will be the root value.

FULL CODE:

#include<bits/stdc++.h>
using namespace std;

struct node
{
  int data;
  node* left;
  node* right;
};

node* insertBST(node* root , int x)
{

    if(root==NULL)
    {
        node* root= new node;
        root->data = x;
        root->left = root->right = NULL;
        return root;
    }
    else
    {
        if(x <root->data)
        {
            root->left = insertBST(root->left , x);
        }
        else
        {
            root->right = insertBST(root->right , x);
        }

    }
}

void inorder(node* root)
{
    if(root)
    {
        inorder(root->left);
        cout<<root->data<<" ";
        inorder(root->right);
    }
}

node* floorValue(node* root, node* prev ,int k)
{
    if(!root){
        return NULL;
    }

    if( !(floorValue(root->left , prev ,k))
    {
        return 0;
    }
    if(root->data == k)
    {
        return root;
    }
    if(root->data > k)
    {
        return prev;
    }
    prev = root;
    return floorValue(root->right , prev , k);
}
int main()
{
    int n;
    cin>>n;
    node *root = new node;
    root = NULL;
    for(int i = 0 ;i<n;i++)
    {
        int k;
        cin>>k;
        root= insertBST(root , k);
    }

    inorder(root);
    
    cout<<"\nEnter the Value for which floor has to be searched : ";
    int k;
    cin>>k;
    
    node* prev = NULL;
    cout<<floorValue(root , prev, k);
    return 0;
}

The code is exactly the same as given in the book except some variable names.

Thank You and thanks in advance.

Answer 1

It's classic Binary Search algorithm. I always recommend you to understand the problem you posted. If you clear with algorithm you will know how Binary Search actualy works, as well as how Backtrack works using StackTrace of your system/computer memory.

Let's dive into that. :)

if(!root){
    return NULL;
}

the above code snippet, is the case, if you reach here, it is guranteed you searched all the possibilities, but didn't find the 'key' you want. :(

if( !(floorValue(root->left , prev ,k))
{
    return NULL; 
}

Remember you should return NULL, instead of return 0, since the return value of your function is actually NULL, (though both 0/NULL defines the false case in c/c++, prematurely you can use any of it.

Now you can see, you are diving into the function, with root->left, means left-part of Tree are checking first, similar to Binary Search, where you are searching left side of your input elements.

if(root->data == k)
{
    return root;
}

If you reach here, congrats, you finally reached into your destination :D, other words, you found your result in huge (or small, whatever) input elements.

if(root->data > k)
{
    return prev;
}

The above snippent is same when your middle elements are greater than your key, so you know you have to go left side of your inputs. (going right will always give you Sadness, you will ended up with nothing).

 prev = root;
return floorValue(root->right , prev , k);

The above code are telling you, you went left, but got 0 (you ended up with failure to find the result), so you need to go right side now.

Now most importantly, understand these two following snippets ::

if(root->data > k)
{
    return prev;
}

and

 prev = root;
 return floorValue(root->right , prev , k);

The above two snippets not only dive you into left or right part of your tree (or inputs) but also checking each and every left and right node of your left Tree, and right and left of your right Tree.

When its failed to get the key you want, it's backtrack to your place where you started to go into LEFT (it's kind of DARK series, let's assume left is PAST here, :D right?? ) now you have to go to future, that's RIGHT, to find out the key.

you get the key ? return it from the left(past), or go to right(future) again.

you will definitely reach a conclusion, either SUCCESS or FAILURE.

enjoy.

Answer 2

The snippet you found is awful, but the answer to your questions is that return 0 is the same as return NULL -- it's not an integer, it's a null pointer. The code is supposed to return null if there is no node in the tree <= the search value.

Here's a much better implementation:

Node* floorNode(Node* tree, int k) {
    Node *flr = NULL;
    while(tree) {
        if (tree -> data <= k) {
            flr = tree;
            tree = tree->right;
        } else {
            tree = tree->left;
        }
    }
    return flr;
}