Skip to Content
CTRL K

Unique Binary Search Trees

Explicación

La observación crucial es que la respuesta para nn nodos es el nn-ésimo número de Catalan.

Demostración

Consideremos un árbol binario de búsqueda (BST) con kk como raíz. En este caso:

  • El subárbol izquierdo tendrá k−1k - 1 nodos con valores menores que kk.
  • El subárbol derecho tendrá n−kn - k nodos con valores mayores que kk.

Como resultado, el problema de contar el número de BST únicos con nn nodos se puede simplificar a contar el número de BST únicos que se pueden construir con k−1k - 1 nodos en el subárbol izquierdo y n−kn - k nodos en el subárbol derecho.

Sea CnC_n el número de BST únicos que se pueden formar con nn nodos. Como la raíz del árbol puede ser cualquiera de los nn valores, obtenemos la siguiente relación de recurrencia:

Cn=∑k=1nCk−1⋅Cn−k C_n= \sum^{n}_{k=1}{C_{k - 1} \cdot C_{n - k}}

que, por inspección, es idéntica a la definición del nn-ésimo número de Catalan.

Implementación

Complejidad temporal: O(N)\mathcal{O}(N)

class Solution {
  public:
	long long nCr(int n, int k) {
		long long res = 1;
 
		// since C(n, k) = C(n, n - k)
		if (k > n - k) { k = n - k; }
 
		for (int i = 0; i < k; i++) {
			res *= (n - i);
			res /= (i + 1);
		}
 
		return res;
	}
 
	int numTrees(int n) { return nCr(2 * n, n) / (n + 1); }
};
class Solution {
	public int numTrees(int n) { return (int)(nCr(2 * n, n) / (long)(n + 1)); }
 
	public long nCr(int n, int k) {
		long res = 1;
 
		// since C(n, k) = C(n, n - k)
		if (k > n - k) { k = n - k; }
 
		for (int i = 0; i < k; i++) {
			res *= (n - i);
			res /= (i + 1);
		}
 
		return res;
	}
}
import math
 
 
class Solution:
	def numTrees(self, n: int) -> int:
		res = math.comb(2 * n, n) // (n + 1)
		return res
Fundamentos