Contar árboles binarios balanceados de altura h

Dada una altura h, cuente y devuelva el máximo número posible de árboles binarios equilibrados con altura h. Un árbol binario balanceado es aquel en el que para cada Node, la diferencia entre las alturas del subárbol izquierdo y derecho no es más de 1.

Ejemplos: 

Input : h = 3
Output : 15

Input : h = 4
Output : 315

Los siguientes son los árboles binarios balanceados de altura 3. 
 

Altura del árbol, h = 1 + max(altura izquierda, altura derecha)
Dado que la diferencia entre las alturas del subárbol izquierdo y derecho no es más de uno, las alturas posibles de la parte izquierda y derecha pueden ser una de las siguientes: 
 

1. (h-1), (h-2)
2. (h-2), (h-1)
3. (h-1), (h-1)

count(h) = count(h-1) * count(h-2) + 
           count(h-2) * count(h-1) + 
           count(h-1) * count(h-1)
        = 2 * count(h-1) * count(h-2) +  
          count(h-1) * count(h-1)
       = count(h-1) * (2*count(h - 2) + 
                          count(h - 1))

Por lo tanto, podemos ver que el problema tiene una propiedad de subestructura óptima.

Una función recursiva para contar no de árboles binarios balanceados de altura h es: 

int countBT(int h)
{
    // One tree is possible with height 0 or 1
    if (h == 0 || h == 1)
        return 1;
    return countBT(h-1) * (2 *countBT(h-2) +
                              countBT(h-1));
}

La complejidad temporal de este enfoque recursivo será exponencial. El árbol de recursión para el problema con h = 3 se ve así: 
 

Como podemos ver, los subproblemas se resuelven repetidamente. Por lo tanto, almacenamos los resultados a medida que los calculamos. 

Un enfoque de programación dinámica eficiente será el siguiente: 

A continuación se muestra la implementación del enfoque anterior:

// C++ program to count number of balanced
// binary trees of height h.
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
  
long long int countBT(int h) {
      
    long long int dp[h + 1];
    //base cases
    dp[0] = dp[1] = 1;
    for(int i = 2; i <= h; i++) {
        dp[i] = (dp[i - 1] * ((2 * dp [i - 2])%mod + dp[i - 1])%mod) % mod;
    }
    return dp[h];
}
 
 
// Driver program
int main()
{
    int h = 3;
    cout << "No. of balanced binary trees"
            " of height h is: "
         << countBT(h) << endl;
}

// Java program to count number of balanced
// binary trees of height h.
class GFG {
     
    static final int MOD = 1000000007;
     
    public static long countBT(int h) {
        long[] dp = new long[h + 1];
         
        // base cases
        dp[0] = 1;
        dp[1] = 1;
         
        for(int i = 2; i <= h; ++i)
            dp[i] = (dp[i - 1] * ((2 * dp [i - 2])% MOD + dp[i - 1]) % MOD) % MOD;
             
            return dp[h];
    }
     
    // Driver program
    public static void main (String[] args) {
        int h = 3;
        System.out.println("No. of balanced binary trees of height "+h+" is: "+countBT(h));
    }
}
/*
This code is contributed by
Brij Raj Kishore
*/

# Python3 program to count number of balanced
# binary trees of height h.
 
def countBT(h) :
    MOD = 1000000007
    #initialize list
    dp = [0 for i in range(h + 1)]
     
    #base cases
    dp[0] = 1
    dp[1] = 1
     
    for i in range(2, h + 1) :
        dp[i] = (dp[i - 1] * ((2 * dp [i - 2])%MOD + dp[i - 1])%MOD) % MOD
     
    return dp[h]
 
#Driver program
h = 3
print("No. of balanced binary trees of height "+str(h)+" is: "+str(countBT(h)))
 
# This code is contributed by
# Brij Raj Kishore

// C# program to count number of balanced
// binary trees of height h.
 
using System;
class GFG {
     
    static int MOD = 1000000007;
     
    public static long countBT(int h) {
        long[] dp = new long[h + 1];
         
        // base cases
        dp[0] = 1;
        dp[1] = 1;
         
        for(int i = 2; i <= h; ++i)
            dp[i] = (dp[i - 1] * ((2 * dp [i - 2])% MOD + dp[i - 1]) % MOD) % MOD;
             
            return dp[h];
    }
     
    // Driver program
    static void Main () {
        int h = 3;
        Console.WriteLine("No. of balanced binary trees of height "+h+" is: "+countBT(h));
    }
    // This code is contributed by Ryuga
}

<?php
// PHP program to count
// number of balanced
 
$mod =1000000007;
 
function countBT($h)
{
    global $mod;
     
    // base cases
    $dp[0] = $dp[1] = 1;
    for($i = 2; $i <= $h; $i++)
    {
        $dp[$i] = ($dp[$i - 1] *
                  ((2 * $dp [$i - 2]) %
                  $mod + $dp[$i - 1]) %
                          $mod) % $mod;
    }
    return $dp[$h];
}
 
 
// Driver Code
$h = 3;
echo "No. of balanced binary trees",
                " of height h is: ",
                    countBT($h) ,"\n";
 
 
// This code is contributed by aj_36
?>

<script>
    // Javascript program to count number of balanced binary trees of height h.
     
    let MOD = 1000000007;
       
    function countBT(h) {
        let dp = new Array(h + 1);
        dp.fill(0);
           
        // base cases
        dp[0] = 1;
        dp[1] = 1;
           
        for(let i = 2; i <= h; ++i)
            dp[i] = (dp[i - 1] * ((2 * dp [i - 2])% MOD + dp[i - 1]) % MOD) % MOD;
               
            return dp[h];
    }
     
    let h = 3;
      document.write("No. of balanced binary trees of height h is: "+countBT(h));
     
</script>

No. of balanced binary trees of height h is: 15

Complejidad de tiempo: O(n)
Complejidad de espacio: O(n)

Enfoque de programación dinámica eficiente en memoria: 

Si observamos cuidadosamente, en el enfoque anterior para calcular dp[i] estamos usando dp[i-1] y dp[i-2] solamente y ya no se requieren dp[0] a dp[i-3]. Por lo tanto podemos reemplazar dp[i],dp[i-1] y dp[i-2] con dp2, dp1 y dp0 respectivamente. (aportado por Kadapalla Nithin Kumar )

Implementación:

// C++ program to count number of balanced
// binary trees of height h.
#include <bits/stdc++.h>
using namespace std;
  
long long int countBT(int h) {
      if(h<2){
      return 1;
    }
      const int BIG_PRIME = 1000000007;
    long long int dp0 = 1, dp1 = 1,dp2;
   
    for(int i = 2; i <= h; i++) {
 
          dp2 = (dp1 * ((2 * dp0)%BIG_PRIME + dp1)%BIG_PRIME) % BIG_PRIME;
       
          // update dp1 and dp0
        dp0 = dp1;
          dp1 = dp2;
 
          // Don't commit following simple mistake
          // dp1 = dp0;
        // dp0 = dp1;
    }
    return dp2;
}
 
 
// Driver program
int main()
{
    int h = 3;
    cout << "No. of balanced binary trees"
            " of height h is: "
         << countBT(h) << endl;
}
// This code is contributed by Kadapalla Nithin Kumar

// Java program to count number of balanced
// binary trees of height h.
class GFG {
     
    static final int BIG_PRIME = 1000000007;
    static long countBT(int h){
        if(h<2){
          return 1;
        }
        long dp0 = 1, dp1 = 1,dp2 = 3;
       
        for(int i = 2; i <= h; i++) {
     
              dp2 = (dp1 * ((2 * dp0)%BIG_PRIME + dp1)%BIG_PRIME) % BIG_PRIME;
           
              // update dp1 and dp0
            dp0 = dp1;
              dp1 = dp2;
     
              // Don't commit following simple mistake
              // dp1 = dp0;
            // dp0 = dp1;
        }
        return dp2;
    }
    // Driver program
    public static void main (String[] args) {
        int h = 3;
        System.out.println("No. of balanced binary trees of height "+h+" is: "+countBT(h));
    }
}
/*
This code is contributed by
Brij Raj Kishore and modified by Kadapalla Nithin Kumar
*/

# Python3 program to count number of balanced
# binary trees of height h.
 
def countBT(h) :
    BIG_PRIME = 1000000007
    if h < 2:
          return 1
    dp0 = dp1 = 1
    dp2 = 3
    for _ in range(2,h+1):
        dp2 = (dp1*dp1 + 2*dp1*dp0)%BIG_PRIME
        dp0 = dp1
        dp1 = dp2
    return dp2
#Driver program
h = 3
print("No. of balanced binary trees of height "+str(h)+" is: "+str(countBT(h)))
 
#This code is contributed by Kadapalla Nithin Kumar

// C# program to count number of balanced
// binary trees of height h.
 
using System;
class GFG {
     
    static int BIG_PRIME = 1000000007;
     
    public static long countBT(int h) {
          // base case
          if(h<2){
          return 1;
        }
 
          long dp0 = 1;
        long dp1 = 1;
        long dp2 = 3;
        for(int i = 2; i <= h; ++i){
            dp2 = (dp1 * ((2 * dp0)% BIG_PRIME + dp1) % BIG_PRIME) % BIG_PRIME;
              dp0 = dp1;
              dp1 = dp2;
        }
       return dp2;
    }
     
    // Driver program
    static void Main () {
        int h = 3;
        Console.WriteLine("No. of balanced binary trees of height "+h+" is: "+countBT(h));
    }
    // This code is contributed by Ryuga and modified by Kadapalla Nithin Kumar
}

<?php
// PHP program to count
// number of balanced
 
$BIG_PRIME =1000000007;
 
function countBT($h)
{
    global $BIG_PRIME;
     
    // base cases
      if($h < 2){
      return 1;
    }
    $dp0 = $dp1 = 1;
    $dp2 = 3;
    for($i = 2; $i <= $h; $i++)
    {
        $dp2 = ($dp1 *
                  ((2 * $dp0) % $BIG_PRIME
                  + $dp1) %
                          $BIG_PRIME) % $BIG_PRIME;
          $dp0 = $dp1;
          $dp1 = $dp2;
    }
    return $dp2;
}
 
 
// Driver Code
$h = 3;
echo "No. of balanced binary trees",
                " of height h is: ",
                    countBT($h) ,"\n";
 
 
// This code is contributed by aj_36 and modified by Kadapalla Nithin Kumar
?>

<script>
    // Javascript program to count number of balanced binary trees of height h.
     
    let BIG_PRIME = 1000000007;
       
    function countBT(h) {
        if(h<2){
            return 1;
        }
        // base cases
        let dp0 = 1;
        let dp1 = 1;
        let dp2 = 3;
        for(let i = 2; i <= h; ++i){
            dp2 = (dp1 * ((2 * dp0)% MOD + dp1) % MOD) % MOD;
            dp0 = dp1;
            dp1 = dp2;
        }
        return dp2;
    }
     
    let h = 3;
      document.write("No. of balanced binary trees of height h is: "+countBT(h));
    // This code is contributed by Kadapalla Nithin Kumar
</script>

No. of balanced binary trees of height h is: 15

Complejidad de tiempo: O(n)
Complejidad de espacio: O(1)

Este artículo es una contribución de Aditi Sharma . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geek.