Finding a cross-link in a binary tree

Question

What will be the most efficient way to find a cross-link in a binary tree ?

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

Now in this tree consider a link between 4 and 5. So how can we find that there is a cross-link from 4 (ie. finding the node from which the cross-link emanates)

(I was asked this question in an interview, btw)

Answer 1

Do a BFS (http://en.wikipedia.org/wiki/Breadth-first_search) and marks visited nodes.

If you ever visit a node already marked as visited then you have a cross-link, and the node from which the cross-link emanates is the one whose children you are exploring.