Trouver un lien croisé dans un arbre binaire

Question

Quel sera le moyen le plus efficace de trouver un lien croisé dans un arbre binaire?

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

maintenant dans cet arbre envisager un lien entre 4 et 5. Alors, comment pouvons-nous trouver qu'il ya une réticuler de 4 (ie. De trouver le noeud à partir duquel la réticuler émane)

(J'ai été posé cette question dans une interview, btw)

Answer 1

Effectuez un BFS (http://en.wikipedia.org/wiki/Breadth-first_search) et marque les nœuds visités.

Si vous visitez un nœud déjà marqué comme visité alors vous avez un lien croisé, et le nœud dont émane le lien est celui dont vous explorez les enfants.