Konwersja drzewa poszukiwań binarnych do listy dwukierunkowej Mariusz: struct Node { int data; struct Node *prev; struct Node *next; }; struct List { struct Node *head; struct Node *tail; }; void BSTtoDLL(struct Node * root, struct List *L) { if(root != NULL) { BSTtoDLL(root−>next,L) ; root−>next = L−>head; if(L−>head != NULL) L−>head−>prev = root; L−>head = root; BSTtoDLL(root−>prev,L); } } 1. Jak zmodyfikować tę funkcję aby ustawiała także ogon listy ? 2. Jak napisać równoważną funkcję w sposób iteracyjny ? w czasie O(n) Tutaj myślałem nad tym aby ostatnie wywołanie rekurencyjne zastąpić pętlą a pierwsze stosem tylko jak to miałoby wyglądać

Mariusz: Jeśli chodzi o ustawianie ogona listy to wystarczy dopisać else do if(L−>head != NULL) if(L−>head != NULL) L−>head−>prev = root; else L−>tail = root; Co z rekurencją ? Drugie wywołanie jest ogonowe i można zamienić je na iterację ale jaki macie pomysł na pierwsze wywołanie ? Najlepiej aby nie tworzyć nowych węzłów i aby funkcja działała w czasie O(n)