JuniorКодОчень частоЕщё не отвечали

Рекурсивный поиск значения в дереве бинарного поиска

Дан корень дерева бинарного поиска. Верните узел со значением target или nullptr, если его нет. Используйте упорядоченность BST для отсечения.

Требования:

меньше значения узла → влево; иначе вправо.

Рекурсивно: пустое поддерево → nullptr; равно → вернуть узел; target
O(h) время, где h — высота дерева (O(log n) при балансе).
Проверяйте nullptr перед разыменованием узла.

struct TreeNode {
    int       val;
    TreeNode* left  = nullptr;
    TreeNode* right = nullptr;
};

TreeNode* search(TreeNode* root, int target) {
    // ваш код здесь
}

Допишите реализацию.

В BST левое поддерево узла содержит меньшие значения, правое — большие. Рекурсивно: пусто → nullptr; равно → вернуть; меньше → влево; иначе вправо. Время O(h): O(log n) при балансе, O(n) в худшем случае.

✗Не проверять nullptr перед обращением к node->val
✗Использовать полный обход дерева вместо свойства BST для отсечения ветвей
✗Забывать, что гарантии BST распространяются на значения, а не на структурный баланс

→Как вставить и удалить узел в BST?
→Что такое AVL-дерево или красно-чёрное дерево и почему они гарантируют O(log n)?

Оглавление

Задача

Напишите рекурсивную функцию поиска значения в дереве бинарного поиска.

Решение

#include <cassert>

struct TreeNode {
    int       val;
    TreeNode* left  = nullptr;
    TreeNode* right = nullptr;
    explicit TreeNode(int v) : val(v) {}
};

// Рекурсивный поиск — O(h), h = высота дерева
TreeNode* search(TreeNode* root, int target) {
    if (!root || root->val == target) return root;
    if (target < root->val) return search(root->left,  target);
    return                         search(root->right, target);
}

// Итеративный вариант (без рекурсии, O(1) стека)
TreeNode* searchIter(TreeNode* root, int target) {
    while (root && root->val != target)
        root = (target < root->val) ? root->left : root->right;
    return root;
}

// Вспомогательная функция вставки для теста
TreeNode* insert(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (val < root->val) root->left  = insert(root->left,  val);
    else if (val > root->val) root->right = insert(root->right, val);
    return root;
}

int main() {
    TreeNode* root = nullptr;
    for (int v : {5, 3, 7, 1, 4, 6, 8}) root = insert(root, v);

    assert(search(root, 4) != nullptr && search(root, 4)->val == 4);
    assert(search(root, 9) == nullptr);
    assert(searchIter(root, 1) != nullptr);
    assert(searchIter(root, 0) == nullptr);
}

Ключевые моменты

BST-поиск исключает половину дерева на каждом шаге благодаря свойству упорядочивания.
Итеративный вариант предпочтительнее для больших деревьев — нет риска переполнения стека.
Для гарантии O(log n) дерево должно быть сбалансированным (AVL, Red-Black, B-tree).

Открыть тему в роадмапе →

Оглавление

Рекурсивный поиск значения в дереве бинарного поиска

Требования:

меньше значения узла → влево; иначе вправо.

Рекурсивно: пустое поддерево → nullptr; равно → вернуть узел; target
O(h) время, где h — высота дерева (O(log n) при балансе).
Проверяйте nullptr перед разыменованием узла.

struct TreeNode {
    int       val;
    TreeNode* left  = nullptr;
    TreeNode* right = nullptr;
};

TreeNode* search(TreeNode* root, int target) {
    // ваш код здесь
}

Допишите реализацию.

Решение

#include <cassert> struct TreeNode { int val; TreeNode* left = nullptr; TreeNode* right = nullptr; explicit TreeNode(int v) : val(v) {} }; // Рекурсивный поиск — O(h), h = высота дерева TreeNode* search(TreeNode* root, int target) { if (!root || root->val == target) return root; if (target < root->val) return search(root->left, target); return search(root->right, target); } // Итеративный вариант (без рекурсии, O(1) стека) TreeNode* searchIter(TreeNode* root, int target) { while (root && root->val != target) root = (target < root->val) ? root->left : root->right; return root; } // Вспомогательная функция вставки для теста TreeNode* insert(TreeNode* root, int val) { if (!root) return new TreeNode(val); if (val < root->val) root->left = insert(root->left, val); else if (val > root->val) root->right = insert(root->right, val); return root; } int main() { TreeNode* root = nullptr; for (int v : {5, 3, 7, 1, 4, 6, 8}) root = insert(root, v); assert(search(root, 4) != nullptr && search(root, 4)->val == 4); assert(search(root, 9) == nullptr); assert(searchIter(root, 1) != nullptr); assert(searchIter(root, 0) == nullptr); }

Ключевые моменты

BST-поиск исключает половину дерева на каждом шаге благодаря свойству упорядочивания.

Итеративный вариант предпочтительнее для больших деревьев — нет риска переполнения стека.

Для гарантии O(log n) дерево должно быть сбалансированным (AVL, Red-Black, B-tree).