Recuento de BST con N Nodes que tienen una altura de al menos K

Dados dos enteros positivos N y K , la tarea es encontrar el número de árboles de búsqueda binarios (BST) con N Nodes de altura mayor o igual a K .

Nota : Aquí la altura se refiere a la profundidad máxima del BST.

Ejemplos :

Entrada : N = 3, K = 3
Salida : 4
Explicación :
Hay 4 posibles árboles binarios de búsqueda con una altura mayor o igual a K.

1 1 3 3                                     
 \ \ / /
  2 3 2 1
   \ | / \ 
    3 2 1 2

Entrada : N = 4, K = 2
Salida : 14

Enfoque : Este problema se puede resolver usando recursividad . Siga los pasos a continuación para resolver el problema:

• Caso base: si N es igual a 1 , devuelve 1 .
• Inicialice una variable countBsts como 0 para almacenar el número de BST válidos .
• Iterar en el rango [1, N] usando la variable i:
  • Si i-1 y Ni es mayor que igual a K , entonces:
    • Llame recursivamente a la función para el subárbol izquierdo, con Nodes como i – 1 y altura como K – 1 , que encontrará el número de formas de crear el subárbol izquierdo .
    • Llame recursivamente a la función para el subárbol derecho con Nodes como N – i y altura como K – 1 que encontrará la cantidad de formas de crear el subárbol derecho.
  • Agregue el resultado en countBsts.
• Después de completar los pasos anteriores, imprima el archivo countBsts.

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number of BST's
// with N nodes of height greater than
// or equal to K
int numOfBst(int n, int k)
{
 
    if (n <= 1) {
        return 1;
    }
 
    // Store number of valid BSTs
    int countBsts = 0;
 
    // Traverse from 1 to n
    for (int i = 1; i <= n; i++) {
        // If Binary Tree with height greater
        // than K exist
        if (i - 1 >= k or n - i >= k)
            countBsts
 += numOfBst(i - 1, k - 1)
 * numOfBst(n - i, k - 1);
    }
 
    // Finally, return the countBsts
    return countBsts;
}
// Driver Code
int main()
{
 
    // Given Input
    int n = 4;
    int k = 2;
 
    // Function call to find the number
    // of BSTs greater than k
    cout << numOfBst(n, k - 1) << endl;
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG
{
 
  // Function to find the number of BST's
  // with N nodes of height greater than
  // or equal to K
  static int numOfBst(int n, int k)
  {
 
    if (n <= 1) {
      return 1;
    }
 
    // Store number of valid BSTs
    int countBsts = 0;
 
    // Traverse from 1 to n
    for (int i = 1; i <= n; i++)
    {
 
      // If Binary Tree with height greater
      // than K exist
      if (i - 1 >= k || n - i >= k)
        countBsts += numOfBst(i - 1, k - 1)
        * numOfBst(n - i, k - 1);
    }
 
    // Finally, return the countBsts
    return countBsts;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
 
    // Given Input
    int n = 4;
    int k = 2;
 
    // Function call to find the number
    // of BSTs greater than k
    System.out.println(numOfBst(n, k - 1));
 
  }
}
 
// This code is contributed by potta lokesh.

# python 3 program for the above approach
 
# Function to find the number of BST's
# with N nodes of height greater than
# or equal to K
def numOfBst(n, k):
    if (n <= 1):
        return 1
 
    # Store number of valid BSTs
    countBsts = 0
 
    # Traverse from 1 to n
    for i in range(1, n + 1, 1):
       
        # If Binary Tree with height greater
        # than K exist
        if (i - 1 >= k or n - i >= k):
            countBsts += numOfBst(i - 1, k - 1) * numOfBst(n - i, k - 1)
 
    # Finally, return the countBsts
    return countBsts
 
# Driver Code
if __name__ == '__main__':
    # Given Input
    n = 4
    k = 2
 
    # Function call to find the number
    # of BSTs greater than k
    print(numOfBst(n, k - 1))
 
    # This code is contributed by bgangwar59.

// C# program for the above approach
using System;
class GFG {
     
  // Function to find the number of BST's
  // with N nodes of height greater than
  // or equal to K
  static int numOfBst(int n, int k)
  {
  
    if (n <= 1) {
      return 1;
    }
  
    // Store number of valid BSTs
    int countBsts = 0;
  
    // Traverse from 1 to n
    for (int i = 1; i <= n; i++)
    {
  
      // If Binary Tree with height greater
      // than K exist
      if (i - 1 >= k || n - i >= k)
        countBsts += numOfBst(i - 1, k - 1)
        * numOfBst(n - i, k - 1);
    }
  
    // Finally, return the countBsts
    return countBsts;
  }
   
  // Driver code
  static void Main()
  {
     
    // Given Input
    int n = 4;
    int k = 2;
  
    // Function call to find the number
    // of BSTs greater than k
    Console.WriteLine(numOfBst(n, k - 1));
  }
}
 
// This code is contributed by divyeshrabadiya07.

<script>
        // JavaScript program for the above approach
 
 
        // Function to find the number of BST's
        // with N nodes of height greater than
        // or equal to K
        function numOfBst(n, k) {
 
            if (n <= 1) {
                return 1;
            }
 
            // Store number of valid BSTs
            let countBsts = 0;
 
            // Traverse from 1 to n
            for (let i = 1; i <= n; i++) {
                // If Binary Tree with height greater
                // than K exist
                if (i - 1 >= k || n - i >= k)
                    countBsts
                        += numOfBst(i - 1, k - 1)
                        * numOfBst(n - i, k - 1);
            }
 
            // Finally, return the countBsts
            return countBsts;
        }
        // Driver Code
 
 
        // Given Input
        let n = 4;
        let k = 2;
 
        // Function call to find the number
        // of BSTs greater than k
        document.write(numOfBst(n, k - 1) + "<br>");
 
    // This code is contributed by Potta Lokesh
 
    </script>

14

Complejidad temporal: O(2 ⁿ )
Espacio auxiliar: O(1)