Problema truefalse-Confronto tra alberi binari

Buongiorno a tutti!
Ho un problema che mi sta facendo impazzire da questa mattina. Ho scritto una funzione che confronta due alberi binari e restituisce true se sono uguali, false altrimenti. Ho anche confrontato la mia con altre funzioni che ho trovato in rete e sono uguali, ma non mi funziona. Il problema è che se il primo nodo dei due alberi è uguale, la funzione restituisce sempre true, anche se poi i sottoalberi (oppure uno dei sottoalberi) sono diversi. Non riesco a capacitarmi perchè provandolo su carta dovrebbe andare. Vi posto la funzione:

bool alberi_uguali(nodo *root1, nodo *root2)   {
	//se entrambi i nodi sono NULL
	if(root1==NULL&&root2==NULL)
		return true;
	//se soltanto uno dei due nodi è NULL
	if(root1==NULL||root2==NULL)
		return false;
	//Se il campo info dei due nodi è diverso
	if(root1->info!=root2->info)
		return false;
	else{
		//ritorna l'and tra il confronto dei sottoalberi dx e sx
		return (alberi_uguali(root1->sx,root2->sx)&&alberi_uguali(root1->dx,root2->dx));
	}

}

la struttura del nodo è:

struct nodo{
	int info;
	nodo *sx;
	nodo *dx;	
};

Volendo fare un esempio banale, voglio confrontare l'albero root1:

 1
  \
   2
    \
     3
         

e l'albero root2

 1
  \
   5
    \
     8
         

Allora ecco il mio ragionamento su carta... Al primo confronto root1->info e root2->info sono uguali, quindi la funzione ritorna l'AND logico tra i sottoalberi sx e dx, cioè:

return (alberi_uguali(root1->sx,root2->sx)&&alberi_uguali(root1->dx,root2->dx))

ed è qui che non riesco a venirne a capo.
La chiamata alberi_uguali(root1->sx,root2->sx) dovrebbe restituire TRUE poichè entrambi i sottoalberi sx sono NULL.
La chiamata alberi_uguali(root1->dx,root2->dx) invece dovrebbe restituire FALSE perchè avrei che root1->info è diverso da root2->info (2 e 5).
Di conseguenza l'AND tra le due funzioni dovrebbe essere (TRUE&&FALSE) e dunque il valore ritornato al main dovrebbe essere FALSE. Invece nel main mi ritrovo TRUE. Se invece il primo nodo dei due alberi è diverso, la funzione restituisce correttamente FALSE.
Sinceramente non riesco proprio a capire cosa non va
Vi posto anche l'intero codice del mio programma:

#include<iostream>
using namespace std;

struct nodo{
	int info;
	nodo *sx;
	nodo *dx;	
};

void tree_insert(nodo *&root,nodo *&nuovo);
void visit(nodo *root);
bool alberi_uguali(nodo *root1,nodo *root2);

int main(){
	nodo *root1=NULL;
	nodo *root2=NULL;
	int n;
	bool uguali;
	
	cout<<"Quanti nodi vuoi inserire nell'albero 1? ";
	cin>>n;
	for(int i=0;i<n;i++){
		nodo *nuovo=new nodo;
		nuovo->sx=NULL;
		nuovo->dx=NULL;
		cout<<"Valore nodo "<<i+1<<": ";
		cin>>nuovo->info;	
		tree_insert(root1,nuovo);
	}
	cout<<"L'albero 1 e' :"<<endl;
	visit(root1);
	cout<<"Quanti nodi vuoi inserire nell'albero 2? ";
	cin>>n;
	for(int i=0;i<n;i++){
		nodo *nuovo=new nodo;
		nuovo->sx=NULL;
		nuovo->dx=NULL;
		cout<<"Valore nodo "<<i+1<<": ";
		cin>>nuovo->info;	
		tree_insert(root2,nuovo);
	}
	cout<<"L'albero 2 e' :"<<endl;
	visit(root2);
	uguali=alberi_uguali(root1,root2);	
	cout<<endl<<uguali<<endl;
	return 0;
}


void tree_insert(nodo *&root,nodo *&nuovo){
	if(root==NULL)
		root=nuovo;
	else{
		if(root->info>=nuovo->info){
			tree_insert(root->sx,nuovo);
		}else{
			tree_insert(root->dx,nuovo);
		}
	}
}

void visit(nodo *root){
	if(root!=NULL){
		cout<<root->info<<endl;
		visit(root->sx);
		visit(root->dx);
	}
	
}


bool alberi_uguali(nodo *root1, nodo *root2)   {
	if(root1==NULL&&root2==NULL)
		return true;
	if(root1==NULL||root2==NULL)
		return false;
	if(root1->info!=root2->info)
		return false;
	else{
		return (alberi_uguali(root1->sx,root2->sx)&&alberi_uguali(root1->dx,root2->dx));
	}

}

GRAZIE A TUTTI!