Эффективный алгоритм, чтобы определить, содержит ли предполагаемое двоичное дерево цикл?

Один из моих любимых вопросов на собеседовании:

За время O (n) и пространство O (1) определить, содержит ли связанный список цикл.

Это можно сделать с помощью Алгоритм поиска цикла Флойда .

Мой вопрос заключается в том, можно ли получить такие хорошие временные и пространственные гарантии при попытке определить, содержит ли двоичное дерево цикл. То есть, если кто-то дает вам определение struct в соответствии со строками

struct node {
    node* left;
    node* right;
};

, насколько эффективно вы можете проверить, что данная структура действительно является двоичным деревом, а не, скажем, DAG или графом, содержащим цикл ?

Есть ли алгоритм, который по корню двоичного дерева может определить, содержит ли это дерево цикл за O (n) раз и лучше, чем за O (n) пространство? Ясно, что это можно сделать с помощью стандартной DFS или BFS, но для этого требуется O (n) пространства. Можно ли это сделать в пространстве O (√n)? O (log n) пробел? Или (Святой Грааль) всего за O (1) пространство? Мне любопытно, потому что в случае связанного списка это можно сделать в пространстве O (1), но я никогда не видел соответствующего эффективного алгоритма для этого случая.