Что такое большой O следующего метода Binary Search Tree

Question

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

    def height(self):
        if self.is_empty():
            return 0
        else:
            left_max = self._left.height()
            right_max = self._right.height()
            return max(left_max, right_max) + 1

Answer 1

• Вы выполняете обход DFS на дереве, все узлы будут посещены только один раз.
• Так что, очевидно, потребуется время только O (N).