Ужасы нашего городка

Мне несколько раз с интервалом от месяцев до лет снился сон на одну и ту же тему, что я второй раз учусь у себя на факе. При этом я осознаю, что учусь второй раз, и, вроде как, непонятно, зачем, но вот учусь. Ну и мысли (все во сне), что как же я сессию сдавать буду, у меня же работа, отпрашиваться надо будет и все такое.
Это я, собственно, к чему. Есть некая девочка, назовем ее Х. (нет, не Хуанита). Девочка учится на программистском факультете. Девочке я до того пытался нести в мозг матан и алгебру, их она сдала.
А вот теперь она попросила помочь с пересдачей по погромированию. Я сначала машинально (девочка позвонила аккурат между двумя нервными совещаниями) попросил прислать все задачи и вопросы, и только потом отметил, что на дворе не то, что февраль, а середина его, и сессия закончилась не только сама, но и вместе с пересдачами. Сталбыть, девочка не то, что с хвостом, а в одном шаге от пресловутого компота.
Ну ладно, слава яйцам, у нее не Паскаль, который я бы без методички не вспомнил (хотя у меня на нем написан один курсач - не мой, и одна лаба - не моя), а старый добрый Це. Ну на Це мы могем, и у нас, естественно, есть муха гэцеце (прольем скупую слезу над безвременно почившим ваткомом, а какой был в свои годы компилятор, какой был слон, какой был слон).
Понятное дело, что ничего эпичного там не было - немного очень простой строковой работы, набившие оскомину фибоначчи и немного работы со связным списком и деревьями (рекурсия, омномном). Ну, короче, один вечер после реально упоротой трудовой недели - могу, значит, еще, на первом курсе учиться.
Девочка то ли гнет дерево не по себе, то ли не познала мантру, что ИТ - это ноулайферство, но в консерватории надо что-то менять. Не мое, впрочем, дело ее жизни учить.

Но фиг с ней, с девочкой, там был интересный вопрос, который я в полубессознанке сделал через жопу, а хотелось красиво. Есть у нас два отсортированных бинарных дерева, нам надо найти мощность пересечения, и нам даже гарантируют, что элементы внутри каждого дерева уникальны.
Вариант через жопу - это пройти одно дерево насквозь и поискать каждый элемент в другом. Были бы это два массива, я бы параллельно по ним прошелся и за один проход все нашел.
Но это деревья, и по условиям задачи (структура данных задана жестко) указателя вверх у нас нет, только налево и направо. В этой ситуации я знаю, как сделать параллельный обход, имея два стека. Но у меня не плюсы, где я взял бы стек из STL и горя не знал, а голая сишка. Писать на автопилоте динамический стек поверх связного списка - ну, это так себе затея в первом часу ночи.
А есть ли более кошерный вариант? Теория-то уверенно говорит, что дерево в глубину без стека не обходится.

Надумал я сейчас только извращенный вариант провязывать стек вызовов указателями (чтобы невозбранно ходить в предыдущие стекфреймы), глубину стека держать как максимум глубин погружения в оба дерева - по сути, эмулируя второй стек на стеке вызовов. При этом что при погружении, что при разматывании то и дело придется "переключать" реальный и эмулируемый стеки. Как-то слишком сложно и кулхацкерски.