Это не домашнее задание, это вопрос интервью.
Ловушка заключается в том, что алгоритм должен быть постоянным. Я довольно не знаю, как это сделать без стека, я бы опубликовал то, что написал, используя стек, но это не имеет никакого отношения.
Вот что я пробовал: я попытался сделать предварительный обход, и я добрался до самого левого node, но я застрял там. Я не знаю, как "перезаписать" резервную копию без указателя стека/родителя.
Любая помощь будет оценена.
(Я отмечаю его как Java с тех пор, что мне удобно использовать, но он довольно язычный агностик, как это видно.)