*Двоичным деревом поиска* (Binary Search Tree, BST) называют двоичное дерево, каждой вершине которой назначено число, которое
больше, чем число, назначенное ее левому потомку, и меньше, чем
число, назначенное ее правому потомку.
Переход за `O(log N)` в худшем случае. Суммарное время обхода с использованием указателя на родителя `O(N)`. Цикл по внешнему итератору легче прервать досрочно, можно комбинировать несколько внешних итераторов (например, сделать слияние двух BST), но работает медленнее внутреннего итератора.
--
Без указателя на родительскую вершину (для дерева без повторяющихся ключей). Суммарное время обхода -- `O(N log N)`.