How to verify if there is a circle in a tree?
-
21-09-2019 - |
Question
Here is a tree:
There will be one root.
Each tree node has zero or more children.
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.
Solution
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.
OTHER TIPS
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.