Finding prime nodes in binary search tree

[dob00000]

Idk any ideas about finding primes node =((

  
#include <iostream>
using namespace std;
struct node
{
    int info;
    node* left, * right;
};
typedef node* Tree;
node* getNode(int x)
{
	node* p = new node;
	if (p != NULL)
	{
		p->info = x;
		p->left = NULL;
		p->right = NULL;
	}
	return p;
}
void insertNode(Tree &T,int x)
{
    if(T)
    {
        if(T->info==x)
        {
            return;
        }
        else if((T->info)>x)
        {
            insertNode(T->left, x);
        }
        else
        {
			insertNode(T->right, x);
		}
    }
    else
    {
        T=getNode(x);
    }
}
void inputTree(Tree &T)
{
    int n,x;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        insertNode(T,x);
    }
}
void LNR(Tree T)
{
    if(T!=NULL)
    {
        LNR(T->left);
        cout << T->info << " ";
        LNR(T->right);
    }
}
node *checkLeft(Tree T){
    if(T!=NULL)return T->left;
    else return NULL;
} 
node *checkRight(Tree T){
    if(T!=NULL)return T->right;
    else return NULL;
}   
int depthOfTree(Tree T)
{
    if(T==NULL) return -1;
    return 1+max(depthOfTree(T->left),depthOfTree(T->right));
}
int countNodes(Tree T){
     
    if(T==NULL) return 0;
    else return (1+countNodes(checkLeft(T))+countNodes(checkRight(T)));
}
void countOdd(Tree T, int &count_odd)
{
    if(T!=NULL)
    {
        if(abs(T->info)%2==1) count_odd++;
        countOdd(T->left,count_odd);
        countOdd(T->right,count_odd);
    }
}
void countEven(Tree T, int &count_even)
{
    if(T!=NULL)
    {
        if(T->info%2==0||T->info==0) count_even++;
        countEven(T->left,count_even);
        countEven(T->right,count_even);
    }
}
int countPositive(Tree T)
{
    {
    if(!T) return 0;
    if(T->info>0) return countPositive(T->left) + countPositive(T->right)+1;
    return countPositive(T->left) + countPositive(T->right);
    }
}
int countNegative(Tree T)
{
    {
    if(!T) return 0;
    if(T->info<0) return countNegative(T->left) + countNegative(T->right)+1;
    return countNegative(T->left) + countNegative(T->right);
    }
}
int check(int x)
{
	if (x < 2)		return 0;
	else if (x>2)
	{
		if (x % 2 == 0) return 0;
		for (int i = 3; i < x; i += 2)  
		{
			if (x%i == 0)  return 0;
		}
	}
	return 1;
}
int countPrime(Tree T)
{
    if(!T) return 0;
    if(check(T->info)==1)  return countPrime(T->left) +countPrime(T->right)+1;
    return countPrime(T->left) +countPrime(T->right);
}
void listPrime(Tree T)
{
    if(T!=NULL)
    {   
        if(check(T->info)==1) cout << T->info << " ";
        listPrime(T->left);
        listPrime(T->right);
    }
}
int main()
{
	Tree T = NULL;
	inputTree(T);
    cout<<"LNR: "; LNR(T); cout<<endl;

	cout<<"Number of nodes: " << countNodes(T)<<endl;
    cout<<"Depth of Tree: "<<depthOfTree(T)<<endl;

    int count_even = 0, count_odd =0;
    countEven(T, count_even);countOdd(T, count_odd);
    cout<<"Number of even nodes: "<<count_even<<endl;
    cout<<"Number of odd nodes: "<<count_odd<<endl;

    cout<<"Number of positive nodes: "<<countPositive(T)<<endl;
    cout<<"Number of negative nodes: "<<countNegative(T)<<endl;

    cout<<"Number of prime nodes: "<<countPrime(T)<<endl;
    cout<<"Prime numbers: "; listPrime(T);
	return 0;
}

[againtry]

https://www.geeksforgeeks.org/print-all-prime-levels-of-a-binary-tree/

[zapshe]

If by prime nodes you mean a node containing a prime number, just go through every node and look for primes?

If you have a search function for this tree, you can loop through a bunch of prime numbers and then search the tree for those particular prime numbers (really only works if you know what range the values in your tree are).

[seeplus]

In C++, use nullptr rather than NULL.

L13 p will never be nullptr (or NULL). If new fails then it will throw an exception.

If you don't want an exception but a nullptr value returned on failure then:

node* p = new(std::nothrow) node;

[jonnin]

finding primes and searching them would be a lot of searches (fast as they are). Interesting... this would be faster if you know something about the data in the tree, and slower if you touch every node for a look or try every prime (esp small values: there is a giant cluster in the first 1000 numbers or so).
another way to do this would be to check the values on insert and mark a member of the node class as prime or not, then just pull them. You may even be able to do something cute like a red-black off primality (??). (Not 100% sure such an abuse would work well... hmm).