Нахождение перекрестной ссылки в двоичном дереве

Question

Какой будет самый эффективный способ найти перекрестную ссылку в двоичном дереве?

        5
      /   \
     3    7
    / \   / \
   2  4  6   8

Теперь в этом дереве рассмотрим связь между 4 и 5. Итак, как мы можем обнаружить, что существует перекрестная ссылка из 4 (т.е. найти узел, из которого исходит перекрестная ссылка)

(кстати, мне задали этот вопрос в интервью)

Answer 1

Сделать BFS (http://en.wikipedia.org/wiki/Breadth-first_search) и пометить посещенные узлы.

Если вы когда-либо посещали узел, уже помеченный как посещенный, то у вас есть перекрестная ссылка, и узлом, из которого исходит перекрестная ссылка, является тот, чьи дети вы изучаете.