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

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

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

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

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

Для гарантированного O(log n) используют самобалансирующиеся деревья (AVL, красно-черные).