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

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

Пример для BST:

boolean contains(Node node, int key) {
    if (node == null) return false;
    if (key == node.key) return true;
    return key < node.key 
        ? contains(node.left, key) 
        : contains(node.right, key);
}

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