Ваша идея кажется правильной.В каждом дереве ведите указатель (итератор).Первоначально итератор должен указывать на самый левый узел дерева.
В каждой итерации выбирайте минимум элементов под тремя указателями тока (это O (1) время и память).Затем поместите этот минимум в результирующий массив.После этого передвиньте соответствующий указатель так, чтобы он указывал на самый левый не посещаемый элемент дерева.Чтобы сделать это в памяти O (1), дерево должно позволить каким-то образом перейти к следующему непосещенному элементу: достаточно иметь указатель на родителя в каждом узле.
Продолжить такие итерациипока не будут посещены все узлы.
Обход целого дерева из n элементов занимает O (n) времени: имеется n-1 ребер, и процесс движется дважды вдоль каждого ребра, один раз вверх и один раз вниз.Таким образом, получающаяся сложность равна 3 * O (n) = O (n).
Алгоритм поиска следующего не посещаемого узла заключается в следующем.Обратите внимание, что когда мы находимся в узле, его левое поддерево уже полностью посещено.Шаги следующие:
Пока нет невидимого правого потомка, подойдите к родителю один раз.Если при этом мы пошли вверх и направо (мы были слева от ребенка), остановитесь прямо у родителя.Если бы мы были в корне, прекратить обход.
Предполагая, что мы еще не остановились, есть правильный ребенок.Иди туда.Тогда, пока есть левый ребенок, идите к левому ребенку.Стоп.
Лучший способ понять это, возможно, визуализировать шаги на некоторой нетривиальной картине бинарного дерева поиска.Например, в статье в Википедии есть пояснительные картинки о обходе дерева .