В BST два узла случайным образом меняются местами, нам нужно найти эти два узла и поменять их местами

Дано бинарное дерево поиска, в котором любые два узла переставлены местами. Итак, нам нужно найти эти два узла и поменять их местами (нам нужно поменять местами узлы,не данные)

Я попытался сделать это, создав дополнительный массив, который имеет неупорядоченный обход дерева, а также сохраняет указатель на каждый узел. Затем мы просто просматриваем массив и находим два узла, которые не в порядке сортировки, теперь эти два узла ищутся в дереве, а затем меняются местами

Итак, мой вопрос: как решить эту проблему в пространстве O (1 )?