Двигаемся по левым ветвям сохраняя указатели на правые узлы (если они есть) в стеке. Как только достигнут лист, вытаскиваем из стека узел, переходим на него и дальше снова движемся по левым ветвям, сохраняя правые узлы в том же стеке. Как только стек опустел - обход дерева закончен.