Witam,
Mam ukorzenione drzewo binarne:
struct TreeNode {
int key; // nalezy zignorowac
TreeNode* left; // lewy syn lub NULL
TreeNode* right; // prawy syn lub NULL
};
TreeNode* root; // korzen
Mam zaprojektować funkcję, która w czasie stałym odpowie na pytanie: czy pewien zadany węzeł x jest przodkiem węzła
y. Na samym początku mogę wykonać pewne obliczenia wstępne (działające w czasie O(n)) i przygotować własne struktury danych (inicjalizacja, preprocessing).
Z góry dzięki za jakieś wskazówki.
Pozdrawiam!