напечатать границу бинарного дерева

Как напечатать внешний кадр бинарного дерева.

1. порядок сверху вниз, слева направо, затем сверху вниз
2. распечатать все самые левые и правые узлы
3. распечатать все конечные узлы

4. распечатать все узлы, имеющие только 1 лист

   100
    / \
   50 150
    / \ /
   24 57 130
    / \ \ \
   12 30 60 132
   

например: вывод должен быть 100, 50, 24, 12, 30, 57, 60, 130, 132, 150

Если мы напишем три разные функции для вывода левых узлов, конечных узлов и правых узлов, это можно легко решить, но для этого потребуется O(n +2logn) время.

Я также ищу подход O(n), но условие состоит в том, что каждый узел должен быть посещен только один раз, не нужна эта дополнительная часть O(2logn).