Traversing n-arry Tree - bez użycia rekruencji i dodatkowych kolekcji

Cześć,
Ostatnio znajomy miał takie zadanie na rekrutacji:
Jest klasa

class TestTree {
        int weight;
        String name;
        List<TestTree> children;
}

Mając takie drzewo, policzyć ile Nodów ma weight > 3. Przy użyciu rekurencji szybko poleci stackoverflow. Osoba rekrutująca powiedziała, że można to rozwiązać używając pointerów. Mowiąc szczerze próbowałem to rozwiązać i jedyne na co wpadłem to takie coś:
Do klasy TestTree musimy dodać dwa pola: TestTree parent raz int indexToProcess. Wtedy taki kod zadziała:

    static void traversall(TestTree root) {
        if (root == null)
            return;
        TestTree current = root;
        while (root.getChildren().size() != root.indexToProcess) {
            if(current.getChildren() != null) {
                if(current.getChildren().size() == current.indexToProcess) {
                    System.out.println("Process " + current.name);
                    current.parent.indexToProcess++;
                    current = current.parent;
                    continue;
                }
                TestTree temp = current;
                current = current.getChildren().get(current.indexToProcess);
                current.parent = temp;
            } else {
                //jestem na samym dole
                System.out.println("Process " + current.name);
                current.parent.indexToProcess++;
                current = current.parent;
            }
        }
        System.out.println("Process " + root.name);
    }

Natomiast mam wątpliwości czy to jest poprawne? Próbowałem rozwiązać to bez dodawania tych zmiennych, ale przy dużym drzewie jak zejdę na sam dół to nie będę w stanie wrócić do góry. Ktoś ma może jakiś inny pomysł?

Jak używasz rekurencję to z automatu dostajesz stos powrotów żeby wiedzieć do którego przodka się cofnąć. Niestety stos systemowy jest mały i zapisuje dużo dodatkowych danych.
Rozwiązanie: stworzyć własny stos. Alokujesz dodatkowy bufor na którym masz stos powrotów (wskaźników na przodków) jako tablicę
Rozwiązanie 2. Nieograniczone wielkością bufora: tworzysz stos powrotów-przodków na liście jednokierunkowej

UPDATE. Nie rozumiem tego dopisku że bez dodatkowej kolekcji. Czy to wymóg rekruterka? Modyfikowanie otrzymanej struktury nie jest uniwersalnym rozwiązaniem bo nie zawsze masz wpływ na tę strukturę, np dostajesz ją z zewnętrznej biblioteki. Niby zawsze można przepisać drzewo ale to już robi się trochę bez sensu bo dwa razy musisz je przejść

Generalnie takie zadania rozwiązuje się przez napisanie procedury succ(node) która zwraca następnika danego węzła.
Do tego potrzebne są link na rodzica parent bo inaczej zadanie jest niemożliwe do realizacji (stos, rekurencja lub te wskaźniki albo jeden wielki H).

succ(node-z-dzieckiem) = zwróć pierwsze dziecko
succ(liść) = po parent wróć do rodzica, ustal którym dzieckiem jest liść, zwiększ indeks; jeżeli nie można zwiększyć indeksu to przyjmi liść = parent i powtórz operację

Potem iterujemy:

curr = root;
do {
  process(curr);
  curr = succ(curr);
} while (curr != root);

Gdy metoda zwróci po raz drugi root to przeszliśmy całe drzewo.

Dekompozycja jest tutaj kluczem do eleganckiego kodziku.

@podroznik: Jeśli chcesz iterować po drzewie, to zamiast rekurencji musisz mieć dodatkową strukturę danych, np., stos - wtedy, jak tutaj, DFS:
https://github.com/lion137/Python-Data-Structures/blob/master/n_ary_trees.py

Ok tak jak myślałem, nie ma możliwości wykonania tego bez posiadania wiedzy o parencie danego noda. Czyli albo robimy dodatkowa kolekcje, a najlepiej kolejke gdzie wkładamy noda podczas "podróży", żeby móc później wrócić.

UPDATE. Nie rozumiem tego dopisku że bez dodatkowej kolekcji. Czy to wymóg rekruterka? Modyfikowanie otrzymanej struktury nie jest uniwersalnym rozwiązaniem bo nie zawsze masz wpływ na tę strukturę, np dostajesz ją z zewnętrznej biblioteki. Niby zawsze można przepisać drzewo ale to już robi się trochę bez sensu bo dwa razy musisz je przejść

Niestety tylko tyle info dostałem, mógł kolega coś przekręcić albo nie dopytał. Sam z ciekawości chciałem zobaczyć czy to po prostu możliwe.
Dzięki za odpowiedzi.

Jak dfs to stos, kolejka to raczej jak szukasz wszerz. BTW w Cracking code interview jest opisany przykład jak to zrobić na wskaźnikach do parenta, co prawda dla binarnego drzewa no ale przerobić to na n odgałęzień nie powinno być problemem.

Chyba da się. N-ary tree, czyli ma limit ilości węzłów podrzędnych, więc można sobie ustalić sposób indeksowania węzłów na danym poziomie, tak jakby były wszystkie możliwe węzły na tym poziomie (indeksy będą miały ew. dziury), i będzie reguła jak się indeks węzła ma do indeksów jego węzłów nadrzędnych aż do roota. Można chodzić kolejnymi poziomami od roota. Wystarczy pamiętać root, bieżący poziom i bieżący indeks w ramach poziomu, i da się trafić w odpowiednie miejsce idąc od roota, choć nie jest to potrzebne za każdym razem. W trakcie trzeba odpowiednio zwiększać indeks (przy dziurach) i ustalać, czy będzie potrzebne przejście na kolejny poziom.

Nie wiem czy tutaj nie ma trochę głuchego telefonu z tym brakiem dodatkowej kolekcji. Referencje na rodzica tez wymagają dodatkowej mapy/tablicy. Takie zadanie standardowo rozwiązuje się bfs/dfs (czyli z pomocnicza kolejka lub stosem), chyba że rzeczywiście jest tutaj jakiś twist.

Jak dodasz jakieś referencje w węźle to i tak złożoność pamięciowa wzrasta. Zamiast referencji na rodzica można dodać referencję na sąsiada na danym poziomie. Można je obliczać na bieżąco. Wtedy iterujesz poziomami. W każdej iteracji trzeba trzymać początek i koniec poziomu niżej, aby go aktualizować.

Można też walnąć tablicę poziomu i podpoziomu. Wtedy nie trzeba nic dodawać w węźle i można się kłócić ze to nie kolekcja ;)