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

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

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

Пример поиска в BST:

public TreeNode search(TreeNode root, int key) {
    if (root == null || root.val == key) {
        return root;
    }
    if (key < root.val) {
        return search(root.left, key);
    } else {
        return search(root.right, key);
    }
}