Задача . D. Сломанное BST

Пусть T — произвольное бинарное дерево, т.е. дерево, у каждой вершины которого не больше двух сыновей. Данное дерево является корневым, т.е существует единственная вершина, у которой нет родителя — корень дерева. В вершинах данного дерева записаны целые числа. Каждое число, которое есть в дереве T попытаются найти следующим алгоритмом:

1. Поставить указатель на корень дерева
2. Сообщить, что число найдено, если значение, записанное в текущей вершине, равно искомому числу
3. Перейти в левого сына вершины, если значение, записанное в текущей вершине, больше искомого числа
4. Перейти в правого сына вершины, если значение, записанное в текущей вершине, меньше искомого числа
5. Сообщить, что число не найдено, если вершина, в которую надо перейти, не существует

Ниже приведен псевдокод описанного алгоритма:

bool find(TreeNode t, int x) {
    if (t == null)
        return false;
    if (t.value == x)
        return true;
    if (x < t.value)
        return find(t.left, x);
    else
        return find(t.right, x);
}
find(root, x);

Данный алгоритм работает корректно, если поиск осуществляется в бинарном дереве поиска (то есть таком дереве, где для каждого узла значение в нем больше значений в его левом поддереве и меньше значений в правом поддереве). На произвольном дереве этот алгоритм, разумеется, может вернуть неправильный результат.

Так как заданное дерево не является в общем случае бинарным деревом поиска, то не все числа возможно найти таким способом. Ваша задача — посчитать, сколько раз найти число не удастся, если алгоритм запущен для всех возможных значений, которые содержатся в дереве.

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