Преобразуйте двоичное дерево в двусвязный список, отслеживая посещенный узел

Учитывая двоичное дерево, задача состоит в том, чтобы преобразовать его в двусвязный список , сохраняя тот же порядок.

• Левый и правый указатели в узлах должны использоваться как предыдущий и следующий указатели соответственно в преобразованной DLL.
• Порядок узлов в DLL должен быть таким же, как и в нордере для данного бинарного дерева .
• Первый узел обхода Inorder (крайний левый узел в BT) должен быть головным узлом DLL.

Следующие два различных решения были обсуждены для этой проблемы.
Преобразование заданного двоичного дерева в двусвязный список | Набор 1
Преобразование заданного двоичного дерева в двусвязный список | Набор 2

Подход: Ниже приведена идея решения проблемы:

The idea is to do in-order traversal of the binary tree. While doing inorder traversal, keep track of the previously visited node in a variable, say prev. For every visited node, make it next to the prev and set previous of this node as prev.

Ниже приведена реализация вышеуказанного подхода:

Примечание. Использование статических переменных, как указано выше, не рекомендуется, здесь статические используются для простоты. Представьте, что одна и та же функция вызывается для двух или более деревьев. Старое значение prev будет использоваться при следующем вызове другого дерева. Чтобы избежать таких проблем, мы можем использовать двойной указатель или ссылку на указатель.

Временная сложность: O(N). Приведенная выше программа выполняет простой неупорядоченный обход, поэтому временная сложность равна O(N), где N — количество узлов в заданном двоичном дереве.
Вспомогательное пространство: O(N), для стека вызовов рекурсии.

Преобразуйте данное двоичное дерево в двусвязный список итеративно, используя структуру данных стека:

Do iterative inorder traversaland maintain a prev pointer to point the last visited node then point current node’s perv to prev and prev’s next to current node. 

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или если вы хотите поделиться дополнительной информацией по теме, обсуждаемой выше.