Алгоритм работает за <tex>O(n)</tex>, так как мы прошлись по дереву два раза за время, равное количеству вершин.
{{Задача
|definition = Выделить в данном дереве наибольшее возможное количество соседних вершин, образующих дерево поиска.
}}
Рассмотрим каждую вершину дерева, предполагая, что она может быть корнем максимального поддерева поиска. Найдём для каждой из них количество всех вершин, которые могут находиться в таком поддереве. Максимальный из результатов, получаемых на каждом шаге, будем запоминать. Вместе с максимумом будем запоминать и соответствующую ему вершину. После того, как мы обошли всё дерево и нашли корень дерева поиска с наибольшим количеством вершин, при помощи обхода <tex>\mathrm{preorderTraversal}</tex> выводим все вершины на экран.
'''Node''' root(Tree[n]: '''Node''') <font color="green">// Tree — заданное двоичное дерево.</font>
maxdp = -1
maxroot = ''null''
'''for''' u '''in''' Tree
dp = dfs(u, <tex> -\infty </tex>, <tex> \infty </tex>)
'''if''' dp > maxdp
maxdp = dp
maxroot = u
'''return''' maxroot
Функция <tex>\mathtt{dfs}</tex> позволяет найти для каждой вершин максимально возможное количество узлов поддерева. На вход функции подаются сама анализируемая вершина и левая и правая границы интервала, в которой могут находиться значения в её поддереве. Начальные значения двух последних аргументов равны <tex> -\infty </tex> и <tex> \infty </tex> соответственно.
В основе функции также лежит [[Обход в глубину, цвета вершин|обход в глубину]]. Рекурсивная функция обходит всех существующих детей вершины, поданной на вход, и, если ребёнок не нарушает условия дерева поиска, она добавляет его в поддерево и анализирует его потомков. В этом случае роль <tex>v</tex> будет разыгрывать ребёнок, удовлетворяющий условию дерева поиска. Если он был левым сыном, то максимально возможному значению присваивается число, стоящее в его родителе, а минимальное возможное значение не изменяется. Наоборот, если он был правым сыном, увеличиваем минимум, а максимум оставляем тем же. В случае, когда левый или правый сын не удовлетворяет условию дерева поиска, этот узел не включается в искомое поддерево и дальше не рассматривается.
Функция возвращает значение переменной <tex>\mathtt{res}</tex>, где записано количество вершин поддерева.
'''int''' dfs(v: '''Node''', max: '''T''', min: '''T''')
res = 1
'''if''' v.left != ''null''
'''if''' v.left.key < v.key '''and''' v.left.key > max
res += dfs(v.left, v.left.key, min)
'''if''' v.right != ''null''
'''if''' v.right.key > v.key '''and''' v.right.key < min
res += dfs(v.left, max, v.left.key)
'''return''' res
Время работы алгоритма {{---}} <tex>O(n^2)</tex>. Существуют также алгоритмы, позволяющие найти поддерево за линейное время.
===Восстановление дерева по результату обхода preorderTraversal===
