¿Cómo podemos encontrar el árbol de búsqueda binario más grande en un árbol binario de manera eficiente?

Puede resolver este problema en tiempo O (N). Para comprender el algoritmo, primero echemos un vistazo a la resolución de este problema donde el BST debe contener la raíz.

Si la raíz debe estar contenida en el BST, entonces si el hijo izquierdo es menor, entonces la raíz deberíamos incluir el hijo izquierdo. Esto se debe a que lo que hacemos a la izquierda de la raíz no puede afectar la derecha de la raíz y viceversa, y de lo contrario terminamos el subárbol. Por lo tanto, es perjudicial no tener un hijo izquierdo / derecho cuando es posible.

Este mismo argumento general se aplica a medida que recurres hacia abajo en el árbol y obtienes restricciones sobre el rango en el que debe estar el nodo del árbol si puedes agregarlo.

Aquí hay un boceto de un algoritmo donde se debe incluir la raíz:

  int resolver (nodo, min_possible, max_possible) {
   if (node! = NULL && min_possible <= node.value && node.value <= max_possible) {
     return 1 + resolver (node.left, min_possible, node.value) + resolver (node.right, node.value, max_possible)
   }
 } 

Este algoritmo se ejecuta en tiempo O (N). Sin embargo, es posible que su árbol de búsqueda no esté enraizado en la raíz de su BST, por lo que deberá hacer O (N ^ 2) de estas búsquedas. Sin embargo, esto se reduce a O (N) utilizando la memorización. Esto se debe a que para un nodo dado solo pueden ocurrir 3 estados posibles de (min_possible, max_possible). Por ejemplo, si el nodo actual es un elemento secundario izquierdo con padre p, los estados son: {(-INF, + INF), (-INF, p.value), (g.value, p.value)} donde g es el antepasado más reciente del que somos el subárbol opuesto de nuestro padre.

Esta publicación a continuación explica tanto O (n ^ 2) como O (n) de manera eficiente
Encuentra el subárbol BST más grande en un árbol binario dado – GeeksforGeeks