CODEWITHSUNDEEP
c++algorithmdata-structuresbinary-treebinary-search-tree
mihir
mihir

Reputation: 15

Finding an element in Binary Search Tree

I wrote this code to find a node in BST.The code works fine for Nodes found but the code crashes when a node is not found.

What is the possible error in my code?

 TreeNode* fetch(TreeNode*root,int d)
    {
                if(root->data==d)
                {

                    return root;
                }
               else  if(root==NULL)
                {

                    return NULL;
                }

                else if(d<root->data)
                {

                    return fetch(root->left,d);
                }
                else if(d>root->data)
                {

                    return fetch(root->right,d);
                }

    }
   TreeNode* temp;
   temp=fetch(root,d);
   if(temp->data)
  {
        cout<<temp->data<<" FOUND";
    }
else if(temp==NULL)
{
    cout<<"Not Found";
}

Upvotes: 0

Views: 2131

Answers (3)

Sanjay Barnwal
Sanjay Barnwal

Reputation: 211

The problem is with the sequence of conditions put in if else if ladder.

Please read the comments I have written on the lines of your code

 TreeNode* fetch(TreeNode*root,int d)
        {
                    if(root->data==d)   /* if d doesn't exists, root becomes 
                                         null and dereferencing a null 
                                         gives error, i.e, null->data is 
                                         error. So, first root=null should 
                                         be checked*/
                    {

                        return root;
                    }
                   else  if(root==NULL)
                    {

                        return NULL;
                    }

                    else if(d<root->data)
                    {

                        return fetch(root->left,d);
                    }
                    else if(d>root->data)
                    {

                        return fetch(root->right,d);
                    }

        }
       TreeNode* temp;
       temp=fetch(root,d);
       if(temp->data)    // temp=NULL should be must codition
      {
            cout<<temp->data<<" FOUND";
        }
    else if(temp==NULL)
    {
        cout<<"Not Found";
    }

Upvotes: 1

littlespice3
littlespice3

Reputation: 141

You have no case if a node is a leaf. Before you call fetch(root->left,d) or fetch(root->right,d) make sure the node has a left or right element by checking if(root->(left/right) != NULL) before you call fetch again. If they do == NULL, then you can return NULL as you've navigated to the bottom of the tree and didn't find your element.

Upvotes: 0

Easton Bornemeier
Easton Bornemeier

Reputation: 1936

You need to adjust your ordering in your fetch() function. Right now, it will error if root==NULL because it first checks if the data in the potentially non-existent node is equal to d. Fixed is as follows: 

TreeNode* fetch(TreeNode*root,int d)
{
            if(root==NULL)
            {

                return NULL;
            }
           else  if(root->data==d)
            {

                return root;
            }

            else if(d<root->data)
            {

                return fetch(root->left,d);
            }
            else if(d>root->data)
            {

                return fetch(root->right,d);
            }

}

Additionally you need to reorder your check at the bottom for the same reason:

if(temp==NULL)
  {
       cout<<"Not Found"; 
    }
else
{
    cout<<temp->data<<" FOUND";
}

Upvotes: 1

Related Questions