Сложность времени общего обхода двоичного дерева

Question

Алгоритм:

Tour (node t)
if t is a leaf node
    visit t
else
    visit t
    Tour(t.left)
    visit t
    Tour(t.right)
    visit t

Сложность кода выше O (n)? где n - количество узлов.

Answer 1

Вопрос: Что вы посещаете?

Если ваша операция посещения t является операцией с постоянным временем и не зависит от размера ввода n, то общая сложность времени этого алгоритма составляет O (n).

Answer 2

Да, каждый узел посещается один раз с постоянным временем доступа.Я предполагаю, что вы имели в виду только одну visit в предложении else, а не 3. Это имеет больше смысла для меня:

Tour (node t)
    visit t
    if t is a leaf node
        return
    Tour(t.left)
    Tour(t.right)