I'm writing a program to print the largest prime in a binary search tree, this is my program:

bool isPrime(int number) {
    bool is_prime = true;

    if (number == 0 || number == 1)
        is_prime = false;

    for (int i = 2; i <= number / 2; i  )
    {
        if (number % i == 0) {
            is_prime = false;
            break;
        }
    }
    return is_prime;
}

BSTNode* largestPrime(BSTNode* root)
{
    BSTNode* temp = new BSTNode;
    temp->data = 0;

    if (root != nullptr) {
        largestPrime(root->left);
        if (isPrime(root->data) && temp->data < root->data)
            temp->data = root->data;
        largestPrime(root->right);
    }
    return temp;
}

But the output is always 0, I don't know how to fix this, can anyone help me solve this problem? Thanks for your help !

CodePudding user response：

First change largestPrime to return an int. Don't know why you made it return a pointer.

Second, don't ignore the return values of the recursive calls to largestPrime. That should have been a red flag.

Something like this

int largestPrime(BSTNode* root)
{
    int max = 0;
    if (root != nullptr) {
        int temp = largestPrime(root->left);
        if (isPrime(temp) && max < temp)
            max = temp;
        if (isPrime(root->data) && max < root->data)
            max = root->data;
        temp = largestPrime(root->right);
        if (isPrime(temp) && max < temp)
            max = temp;
    }
    return max;
}

UPDATE

Here's a similar version that returns a pointer to the node containing the largest prime.

BSTNode* largestPrime(BSTNode* root)
{
    BSTNode* max = nullptr;
    if (root != nullptr) {
        BSTNode* temp = largestPrime(root->left);
        if (temp && isPrime(temp->data) && (max == nullptr || max->data < temp->data))
            max = temp;
        if (isPrime(root->data) && (max == nullptr || max < root->data))
            max = root->data;
        temp = largestPrime(root->right);
        if (temp && isPrime(temp->data) && (max == nullptr || max->data < temp->data))
            max = temp;
    }
    return max;
}

CodePudding user response：

I'd start with isPrime to make it a little bit faster and easier to read:

bool isPrime(int number) {
    if (number <= 1) return false; // negatives, 0 and 1 are not primes
    if (number == 2) return true;
    if ((number&1) == 0) return false; // even numbers are not primes, except 2
    
    for (int i = 3; i <= number / 2; i =2) // check only odd numbers
        if (number % i == 0) return false;
    return true;
}

next step is to fix largest prime search:

BSTNode* largestPrime(BSTNode* root)
{
    if (root != nullptr) {
        BSTNode* maxPrime = isPrime(root->data) ? root : nullptr;
        
        BSTNode* maxLeftPrime = largestPrime(root->left);
        if (maxLeftPrime != nullptr && (maxPrime == nullptr || maxLeftPrime->data > maxPrime->data)) 
            maxPrime = maxLeftPrime;

        BSTNode* maxRightPrime = largestPrime(root->right);
        if (maxRightPrime != nullptr && (maxPrime == nullptr || maxRightPrime->data > maxPrime->data)) 
            maxPrime = maxRightPrime;

        return maxPrime;
    }
    return nullptr;
}

if you have actual binary search tree, where max(left->data) <= node->data <= max(right->data) then you can optimize function a little bit:

BSTNode* largestPrime(BSTNode* root)
{
    if (root != nullptr) {
        BSTNode* maxRightPrime = largestPrime(root->right);
        if (maxRightPrime != nullptr) return maxRightPrime;

        if (isPrime(root->data)) return root;
        
        BSTNode* maxLeftPrime = largestPrime(root->left);
        if (maxLeftPrime != nullptr) return maxLeftPrime;
    }
    return nullptr;
}

CodePudding user response：

You should make use of the BST property: since an in-order traversal will visit its values in sorted order, you could do an inverse in-order traversal, and at the first prime you find you can exit the recursion and return it all the way to the initial caller. Because of the BST order, you know this will be the greatest prime in the tree.

BSTNode* largestPrime(BSTNode* root)
{
    BSTNode* max = nullptr;
    if (root != nullptr) {
        BSTNode* temp = largestPrime(root->right);
        if (temp != nullptr) // Found it in subtree, get out of here.
            return temp;
        if (isPrime(root->data))
            return root; // Found it
        return largestPrime(root->left); // Not found yet, try left
    }
    return nullptr; // No prime found
}