Searching in recursive Binary Search Tree

Question

I am using Recursion to search an element in my Binary Search Tree but my code stops working if the element is not present in the BST.

void tree::searching(node *root,int key)
{
    if(root->key==key||root==NULL)
    {
       cout<<"Congratulation Element found in the BST"<<"\n";
       return;
    } else {
        if(key<root->key)
        {
           searching(root->left,key);
        } else {
           searching(root->right,key);
        }
    }
}

Answer 1

You're dereferencing a NULL pointer here:

if(root->key==key||root==NULL)
{
    cout<<"Congratulation Element found in the BST"<<"\n";
    return;
}

The || operator evauates the left side first, and if it is value then it evaluates the right side. So you dereference root before checking if it is NULL.

Do the NULL check first and return if you find a NULL pointer:

void tree::searching(node *root,int key)
{
    if (root == nullptr) {
        return;
    }

    if(root->key==key) {
        cout<<"Congratulation Element found in the BST"<<"\n";
    } else if(key<root->key)
        searching(root->left,key);
    } else {
        searching(root->right,key);
    }
}

Answer 2

The problem

If root would be nullptr in this statement:

    if(root->key==key||root==NULL)

you would first dereference a null pointer with root->key, which is UB, before checking if it's NULL.

The solution

Do it the other way round:

    if(root==nullptr||root->key==key)

In this case, if root is NULL, the the if clause is immediately executed. Only if root would be not NULL, would the pointer be dereferenced.

Note: you tell that the element was found even if the element is not found (i.e. root reached a nullptr, without ever having encountered the correct key). Consider having distinct case for nullptr (means that it was not found), and equality (means that it was found).

Answer 3

You are printing too early. If the programs go to a leaf it will print because the expression in the fist if will be evaluated to true.

void tree::searching(node *root,int key)
{
    if (root == nullptr)
    {
        return;
    }
    if(root->key==key)
    {
        cout<<"Congratulation Element found in the BST"<<"\n";
        return;
    }
    else
    {
        if(key<root->key)
        {
            searching(root->left,key);
        }
        else
        {
            searching(root->right,key);
        }
    }

 }