Permutacje tworzące to samo drzewo BST

Witam!

Jak najefektowniej mogę sprawdzić które z permutacji jakiegoś dowolnego słowa stworzą to samo drzewo BST? Można tworzyć drzewo i porównywać wyjście inorder np ale to raczej będzie czasochłonne dla wejścia np 25 elementowego co daje 25! permutacji. pÓÓÓÓki co wymyśliłem że pierwsza litera zawsze musi być ta sama ponieważ będzie wstawiana jako korzeń drzewa, ale przy 25 elementach to i tak zostaje 24! permutacji.

Może podaj na przykładzie 3-literowego słowa.

Nie wiem jaki to ma cel ale ok :D Słowo NOGA. Mamy 4! permutacji, a identyczne drzewo utworzymy z 3 permutacji tego zbioru NGAO NGOA NOGA

A z pozostałych 20 permutacji nie utworzymy identycznego drzewa?
Może chodzi ci o jakieś specjalne zasady budowania takiego drzewa o których nić nie mówisz.

Może nie wspomniałem ale jeśli mamy słowo NOGA to wstawiamy pojedyncze litery od lewej do prawej na drzewo więc mając NOGA (N będzie wstawione jako korzeń). Mając permutacje OGAN (O będzie korzeniem więc to będzie inne drzewo). Może kod Insert wstawię

 
	 void insert (char x) {
			
			Node s, p, prev; // zmienne referencyjne
			s = new Node() ; // utwórz nowy węzeł
			s.info = x ; s.left= null; s.right= null;
			
			if (root == null) root = s; // drzewo pust
			
			else {
					
				p = root; prev = null; // bieżący i popr
	
				while ( p != null ) {
						
					prev = p;
						
					if ( x < p.info )	p = p.left;
							else
										p = p.right;
			     } 

			
				if ( x < prev.info ) prev.left= s;
			
				else 
									 prev.right = s;
			}
	} 
	 

1. Dla pierwszego słowa zbuduj drzewo.
2. Tworzysz listę składającą się z jednego węzła - korzenia.
3. Jeżeli kolejna litera sprawdzanego słowa nie jest na liście węzłów to koniec - słowo tworzy inne drzewo
4. Usuń ten węzeł z literą z listy zaś dodaj bezpośrednich potomków tego węzła
5. Przejdź do pkt 3.

Łatwo można odwrócić ten algorytm.

1. Na początku tworzymy listę składającą się z liści drzewa
2. Iterujemy sprawdzane słowo od końca
3. Dodajemy do listy węzeł kiedy znikną z listy wszystkie jego potomkowie.

Bardzo łatwo z tego pierwszego zapisu zrobić wyrażenie RegEx

Ok ale w jakieś kolejności wstawiać potomków do listy? Najpierw lewego a później prawego czy odwrotnie? Będzie to miało jakieś znaczenie?