単方向リンクトリストがループしていることを検出する巧妙なアルゴリズムとして、ポインタを2個用意し、片方をひとつずつ、もう片方はふたつずつ進めてゆき、同じノードを指すようなことが起きたらループしている、というものがあります。
これを木に対して拡張することを考えます。木の場合は、片方の部分木に対して再帰した後、残りの部分木について再帰する必要があるので（ポインタ付換え法といった特殊なテクニックにより絶対に不可能でもないですが）、木の深さに対応した追加記憶は必要になりますが、枝をたどる順序を一意に決めることができれば、同じ考え方が使えるはずです。
ただし、次のような場合にループは無いにもかかわらずfalse positiveになってしまいます。ループにはなっていないが複数のエッジがノードを共有している場合（DAGになっている場合）に、違う枝を探索中のそれぞれのポインタが、偶々同じタイミングで共有されているノードを指してしまった場合です（共有があれば必ず起きるわけではない）。
Pythonのジェネレータを使うとわかりやすく記述できるため、Pythonでサンプルを書きました。
