A che ora in termini di Big O occorrerà unire due BST in One? Ciascuno che non ha né nodi né altezza O (log n) senza elementi comuni.
Il risultato dovrebbe essere anche un BST
Il post StackOverflow che @manlio ha indicato è un duplicato esatto. Fondamentalmente, sì, l'algoritmo può essere migliorato a O (n + m); l'approccio è quello di appiattire gli alberi in liste ordinate, unirle e ricreare un BST. Questa pagina ha anche qualche codice di esempio che potrebbe essere di interesse pure.
Leggi altre domande sui tag c++ data-structures binary-tree