необходимо найти вершину в поисковом бмнарном дереве с минимальным ключом, через которую проходит четное число путей максимальной длины(максимальная длина пути в дереве дана).

Если кто подскажет алгоритм, буду очень благодарен.

Здравствуйте, werdex86, Вы писали:

W>необходимо найти вершину в поисковом бмнарном дереве с минимальным ключом, через которую проходит четное число путей максимальной длины(максимальная длина пути в дереве дана).

Не понял: максимальная длина пути задаётся независимо, или это заранее найденная характеристика данного дерева?
Склоняюсь ко второму.

---

Выполняем обход Left-Right-Parent (иллюстрация)
Попутно измеряем глубину погружения в каждый момент.

Тем самым, мы находим:
— Листья, лежащие на максимальной глубине
— Для каждого узла — количество таких листьев в его поддереве. (Достаточно находить чётность).
Как только мы нашли узел с чётностью=0 (кстати: если через узел не проходит ни одного максимального пути — он нам подойдёт?), идём от него влево-вверх и продолжаем находить чётность. Вправо-вверх идти смысла нет, поскольку нам надо найти минимальный ключ.

            /
           x (4) а этот родитель и все остальные узлы - правее найденного, так что остановимся на них
    ______/ \
   *        ...
  / \
...  *       (3) слева от него остались непроверенными несколько родителей *, поднимаемся влево-вверх
    / \
  ...  0     (2) тогда узел "чётный"
      / \
     1   1   (1) оба поддерева - "нечётные"
    ... ...

Итого, нам нужно 1..N булевых флажков, обозначающих чётность посещённых узлов.