How to verify if there is a circle in a tree?

Question

Here is a tree:

1. There will be one root.

2. Each tree node has zero or more children.

3. It is allowed that two nodes points to the same child. Say, both node A and node B has child C.

However, it is prohibited that,

Node A is an offspring of Node B, and Node B is an offspring of Node A.

One prohibited case is

Node A has a child Node C and Node D,

Both Node C and D has a child node E,

Node E has a child of A.

The question is, how to determine this circle in a fastest manner?

UPDATE: I realize this is to find any cycle in a directed graph. Just now I managed to think out a solution similar to Tarjan's algorithm.

Thanks for comments.

Answer 1

circles can be found using 2 pointers and advancing them at different intervals. Eventually the pointers will match, indicating a loop, or the "faster" one will reach then end. The question is usually asked of linked lists though, not trees.

Answer 2

Do a Depth First Search through the tree. If at any point you find a node that is already in your backtracking stack, there is a circle.