Search a Tree for a Value

Question

I am really stuck on trying to figure this out. This is the tree:

            5
          /  \
         4    8
        /    /  \
       11    13  4
     /   \        \
    7     2        1

Question: Create a function to search for a value in the binary tree given above. The function should return a pointer to that node if the value is found; otherwise the function should return a null pointer. The parameters should be a pointer to the root node of the binary tree and a value to be searched.

BinaryTree *search_for_val(BinaryTree *bt, int val)
   {
      if(!bt->isEmpty())
      {
         if(bt->getData() == val)
            return bt;
         else
            return search_for_val(bt->right(), val);
         return search_for_val(bt->left(), val);
      }
   }

I've successfully created the tree and everything else works fine. It's just this. There's no compile or run time error. It's logic I guess...I changed it around so many times but it seems like if the right nodes are displayed, then the left nodes won't be and vice versa. Please help me.

Thank you so much for the responses. I understand where I went wrong and appreciate your help. I've got another question...I could have posted again but it's kinda related to this one. I'm really sorry if this is violating the rules of posting. I'll take it down and post again if this is so.

Question:

I have to create a function to delete the leaf nodes.

The function will take in a pointer to the root node of the binary tree and a value to be deleted. If the value passed in the function is not a leaf then the function should display an appropriate message. Otherwise the function should delete a node with that value

void delete_val(BinaryTree *bt, int val)
{
    BinaryTree *temp;
    temp = search_val(bt, val);
    //cout << "   " << temp->left()->getData() << " " << temp->left()->getData() << endl;
    if(temp->isLeaf())
    {
        delete temp;
        cout << "   Leaf " << temp->getData() << " deleted" << endl;
    }
    else { cout << "   " << val << " is not a Leaf" << endl; } 
} 

I used the answer you provided for the search_val function to solve this one. The problem is that when I want to delete an actual leaf, it still prints that it is not a leaf. I think it's coming from my is_Leaf function but can't pinpoint exactly what's wrong.This is my is_Leaf function:

bool BinaryTree::isLeaf()
{
    return ((this->leftTree == NULL) && (this->rightTree == NULL));
}

leftTree and rightTree are private members of my BinaryTree class. Can you see anything?

Thanks.

Answer 1

Your logic can never search down the left tree. If the right search fails, you need to return the left tree.

BinaryTree *search_for_val(BinaryTree *bt, int val)
   {
      BinaryTree *result;
      if(bt->isEmpty()) // Reverse sense of test.
         result = nullptr;
      else if (bt->getData() == val)
         result = bt;
      else
         result = search_for_val(bt->right(), val);
         if (result == nullptr)
             result = search_for_val(bt->left(), val);

      return result;
   }

Answer 2

The function is missing the return statement if bt is empty. Furthermore, due to the return statement, the last branch is not reached. Thee function might also crash if bt is null. This can be changed as follows.

BinaryTree *search_for_val(BinaryTree *bt, int val)
{
    BinaryTree* Result = null;
    if( null != bt && !bt->isEmpty() )
    {
        if( bt->getData() == val )
        {
            Result = bt;
        }
        else
        {
            Result = search_for_val( bt->right(), val );
            if ( null == Result )
            {
                Result = search_for_val( bt->left(), val );
            }
        }
    }
    return Result;
}