Drzewo binarne - czy x jest przodkiem y w czasie stałym

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!

Wydaje mi się, że sposobu ogólnego nie ma, tzn. nie da się tego zrobić w czasie stałym dla dowolnego drzewa binarnego. Najlepszy pomysł jaki mam jest O(h) gdzie h to wysokość drzewa.

Edit: A jednak nie zastanowiłem się nad tym wystarczająco.

Aby odpowiedzieć w czasie stałym na zapytanie czy węzeł x jest przodkiem węzła y musisz wstępnie przeszukać drzewo w głąb i wykonać dwie operacje:

• dla każdego węzła obliczasz rozmiar poddrzewa tego węzła (jeżeli nie ma potomków to rozmiar = 1);
• ponumerować wierzchołki w porządku preorder (czyli tak jak idzie przeszukiwanie w głąb).

Teraz dzięki jednemu warunkowi (który pozostawiam ci do napisania) będziesz mógł odpowiedzieć na zapytanie w czasie stałym.