Задачи модуля "Деревья поиска": от проверки дерева до общего предка

Достаточно ли просто проверить, что для каждого узла left->key < node->key и right->key > node->key?

Нет, просто проверять непосредственных потомков недостаточно! Может случиться так, что в правом поддереве (где все ключи должны быть больше корня) где-то глубоко внизу находится узел с очень маленьким ключом, который нарушает глобальное свойство дерева.

Правильный подход - передавать при рекурсивном обходе допустимые границы (диапазон [min_val, max_val]) для каждого узла. Изначально для корня диапазон от минус бесконечности до плюс бесконечности. Когда мы идем влево, верхняя граница становится равна ключу текущего узла. Когда идем вправо, нижняя граница становится равна ключу.

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>

typedef struct node {
        int key;
        struct node *l, *r;
} node;

/* Вспомогательная рекурсивная функция с границами */
bool isBSTUtil(node* root, int min_val, int max_val) {
        if (root == NULL) {
            return true;
        }
    
        /* Если узел нарушает границы, это не BST */
        if (root->key <= min_val || root->key >= max_val) {
            return false;
        }
    
        /* Проверяем левое поддерево (ограничиваем максимум) 
           и правое поддерево (ограничиваем минимум) */
        return isBSTUtil(root->l, min_val, root->key) && 
               isBSTUtil(root->r, root->key, max_val);
}

/* Главная функция */
bool isBST(node* root) {
        return isBSTUtil(root, INT_MIN, INT_MAX);
}

В обычном дереве это сложная задача, требующая обхода. Как свойство дерева поиска может помочь сделать это за один проход от корня вниз?

Благодаря свойству дерева поиска, задача решается чрезвычайно просто. Мы начинаем спускаться от корня:

1. Если ключ текущего узла больше и A, и B, значит, оба узла находятся в левом поддереве. Идем влево.
2. Если ключ текущего узла меньше и A, и B, значит, оба узла в правом поддереве. Идем вправо.
3. Если ключ текущего узла оказался между A и B (включительно), значит, пути к узлам расходятся именно здесь! Это и есть искомый LCA.

Этот алгоритм работает за время O(h), где h - высота дерева.

#include <stdio.h>

typedef struct node {
        int key;
        struct node *l, *r;
} node;

/* Итеративный поиск LCA в BST */
node* findLCA(node* root, int a, int b) {
        /* Если дерево пустое */
        if (root == NULL) return NULL;
    
        while (root != NULL) {
            /* Если оба ключа меньше корня, идем влево */
            if (a < root->key && b < root->key) {
                root = root->l;
            }
            /* Если оба ключа больше корня, идем вправо */
            else if (a > root->key && b > root->key) {
                root = root->r;
            }
            /* Иначе мы нашли точку расхождения */
            else {
                break;
            }
        }
        return root;
}