Problema su albero binario senza ribilanciamento

Giorno a tutti, io ho un piccolo problema con il seguente codice:

struct alb{
	unsigned int chiave;
	alb *sx, *dx;
};

void Inserisci(alb *&a, unsigned int chiave){
	if (a == NULL){
		a = new alb;
		a->chiave = chiave;
		a->sx = a->dx = NULL;
		return;
	}
	if (chiave < a->chiave)
		Inserisci(a->sx, chiave);
	if (chiave > a->chiave)
		Inserisci(a->dx, chiave);
}

int Stampa_S_D(alb *&a, const unsigned int K){
	unsigned int ssx = 0, sdx = 0;
	if (a->sx != NULL)
		ssx = Stampa_S_D(a->sx, K);
	if (a->dx != NULL)
		sdx = Stampa_S_D(a->dx, K);
	if (ssx*K < sdx)
		cout << a->chiave << '\n';
	return ssx + sdx + a->chiave;
}

Il problema mi chiede questo:

Ovviamente il seguente codice non mi stampa in ordine crescente le chiavi dei nodi che rispettano la regola P, perché dovrei inserire la "cout" nel mezzo alle due visite.
Però non posso farlo perché prima di fare il confronto della regola P devo per forza visitare il sottoalbero destro di ogni nodo.

Avevo pensato di aggiungere nella struct 2 variabili 'S' e 'D' cosi da poterle calcolare con una specie di funzione di refresh ricorsiva e dopo stampare le chiavi che rispettavano la regola P con un'altra funzione di stampa molto semplice:
Visita sinistra
cout
Visita destra

Però non credo sia accettato nel compito d'esame e se la complessità rimane lineare nel numero di nodi.

Secondo voi cosa potrei fare? che alternative ho?
Vi ringrazio per l'aiuto.