Реализация функции подсчёта листовых узлов в бинарном поисковом дереве

Условие

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

Ответ

Верните 0 для пустого дерева и 1 для узла без детей. Для остальных узлов результат равен сумме количества листьев слева и справа; значение ключа не влияет на подсчёт.

std::size_t countLeaves(const Node* root) {
    if (!root) return 0;
    if (!root->left && !root->right) return 1;
    return countLeaves(root->left) + countLeaves(root->right);
}

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