Какая алгоритмическая сложность поиска элемента в бинарном дереве

В среднем случае поиск элемента в сбалансированном бинарном дереве имеет сложность O(log n), где n — количество узлов. Это происходит потому, что на каждом шаге алгоритм отбрасывает половину оставшихся элементов.

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

Пример для сбалансированного дерева:

def search(root, key):
    if root is None or root.val == key:
        return root
    if root.val < key:
        return search(root.right, key)
    return search(root.left, key)

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