How to find the leaf of a binary tree?

Question

I am writing a binary tree with a search function. The function is supposed to take an argument x which denotes the value to be searched and once it is found, determine if it is a leaf or not. If the value is not found, the search functions returns false.

Here is what I have which gives me a seg fault and has been just giving me false returns for every value from 1 to 100. The binary tree is initalized with 100 values.

bool search(Node<T>* &currentNode, const T& x) const
{
    //~ cout << "CURRENT NODE DATA: " << currentNode->data << "   :   ";


    /*  FUNCTION: Searches for variable that is passed in X and checks if this value is a leaf or not */

    //Left Subtree Search
    if (x < currentNode->data)
    {

    if ((leaf(currentNode)) == true)
        { 
          return true;
        }
    else 
    {
    search(currentNode->left, x);   

    }

    }


//Right Subtree Search
else if (x >= currentNode->data)
{

    //If node in right subtree is a node check 
    if ((leaf(currentNode)) == true)
    {
        return true;
    }   

    else 
    {
    search(currentNode->right, x);
    }

}




 //Return false if the node is not a leaf
 return false;

}  //END OF SEARCH FUNCTION



void remove(Node<T>* &currentNode, const T& x)
{

}

bool leaf(Node<T>* currentNode) const 
{
    if (currentNode != nullptr)
    {
    return ((currentNode->left == nullptr && currentNode->right == nullptr) ? true : false);        
    }
    else 
    {
        return true;
    }
}

Answer 1

Additionally, the leaf function returns true when currentNode is nullptr, assuming the check for nullptr in search is resolved. Is this the behavior you want for a pointer pointing to a non-existent leaf?

Answer 2

In your search function, you recourse on the child nodes without seeing if they're nullptr first... Then you try to de reference the data element still without checking for null.