Поиск узла в бинарном дереве поиска

Условие

Создайте функцию, получающую в качестве параметров указатель на корневой элемент BST и значение, которое необходимо найти. Функция должна пройти по дереву в поисках указанного значения и вернуть указатель на найденный узел, либо nullptr, если такой узел отсутствует.

Ответ

На каждом шаге сравнивайте цель со значением узла: при меньшем значении идите влево, при большем — вправо. При совпадении верните узел, при достижении пустой ветви — nullptr.

Для Node с полями value, left и right:

Node* findNode(Node* root, int target) {
    while (root) {
        if (root->value == target) return root;
        root = target < root->value ? root->left : root->right;
    }
    return nullptr;
}

Алгоритм использует свойство BST; для произвольного бинарного дерева он неверен. Время O(h), где h — высота: O(log n) для сбалансированного дерева и O(n) для цепочки. Дополнительная память O(1).