Худшая временная сложность BST (прохождение через порядок)

Question

Рассмотрим временную сложность обхода после заказа в двоичном дереве поиска N узлы. Я знаю, что это занимает O(N) для посещения всех узлов, в общем случае, но какова сложность в худшем случае, когда BST является списком? Я думаю, что это займет O(N^2)потому что это будет проходить N узлы идти до конца, и N узлы, чтобы вернуться к началу. Это означает N*N = N^2так что я думаю это O(N^2), Это правильно?

Answer 1

В вашем "наихудшем" сценарии (который я, честно говоря, не понимаю) это N + N = O(N), а не N * N = O(N^2).