Месье, ваши problem solving skills не на высоте, или как я провалил одно собеседование

Вы неправы, вот доказательство ideone.com/OjNWMU.
Расход памяти вычисляется как максимальный размер стека, и равен он, как несложно догадаться, глубине дерева, которая для сбалансированного бинарного дерева равна log₂N.

Месье, ваши problem solving skills не на высоте, или как я провалил одно собеседование

Рекурсивное решение с использованием стека.

struct leaf {
    public:
        int value;
        leaf* right;
        leaf* left;
        leaf* neighbor;

        leaf(int v, leaf* r, leaf* l) :
            value(v), right(r), left(l), neighbor(nullptr) {};
};

void find_neighbors(leaf* node, std::stack<leaf*> & stack)
{
    if (node == nullptr) {
        return;
    };

    if (!stack.empty()) {
        node->neighbor = stack.top();
        stack.pop();
    };

    find_neighbors(node->right, stack);
    find_neighbors(node->left, stack);
    stack.push(node);

    return;
}

Сложность O(N), память O(logN).

LIVR — «независимые от языка правила валидации» или валидация данных без «проблем»

И всё же «валидатор не должен делать ничего кроме валидации» (принцип единственной ответственности).
Пример, показывающий зависимость результата валидации от порядка следования правил, «хорошие валидаторы» так не делают.

Безумный PHP. Фьюри код

> PHP видит 0 и думает что это число.
Здесь вы немного неправы. PHP видит 0e[0-9]+ и думает что это float число, которое приводится к 0. Подробнее вот здесь blog.whitehatsec.com/magic-hashes

Тостер. Коллективное редактирование вопросов

да, в ctype_alnum(), т.к. эта функция не работает с utf-8