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