Número de árboles binarios para una longitud de secuencia de preorden dada

Cuente el número de árboles binarios posibles para una determinada longitud de secuencia de preorden n.
Ejemplos: 
 

Input : n = 1
Output : 1

Input : n = 2
Output : 2

Input : n = 3
Output : 5

Fondo :

En Preorder traversal , primero procesamos el Node raíz, luego recorremos el Node secundario izquierdo y luego el Node secundario derecho. 
Por ejemplo, el recorrido de pedido anticipado del árbol a continuación es 1 2 4 5 3 6 7 
 

Encontrar el número de árboles con Preorder dado:

Número de árboles binarios posibles si se proporciona tal longitud transversal (digamos n).
Tomemos un ejemplo : Secuencia de preorden dada -> 2 4 6 8 10 (longitud 5). 
 

• Suponga que solo hay 1 Node (es decir, 2 en este caso), por lo que solo es posible 1 árbol binario
• Ahora, suponga que hay 2 Nodes (es decir, 2 y 4), por lo que solo son posibles 2 árboles binarios:
• Ahora, cuando hay 3 Nodes (es decir, 2, 4 y 6), entonces el árbol binario posible es 5
• Considere 4 Nodes (que son 2, 4, 6 y 8), por lo que el árbol binario posible es 14. 
  Digamos que BT (1) denota el número de árbol binario para 1 Node. (Suponemos BT(0)=1) 
  BT(4) = BT(0) * BT(3) + BT(1) * BT(2) + BT(2) * BT(1) + BT(3) * BT(0) 
  BT(4) = 1 * 5 + 1 * 2 + 2 * 1 + 5 * 1 = 14
• Del mismo modo, considerando todos los 5 Nodes (2, 4, 6, 8 y 10). El número posible de árbol binario es: 
  BT(5) = BT(0) * BT(4) + BT(1) * BT(3) + BT(2) * BT(2) + BT(3) * BT(1) ) + BT(4) * BT(0) 
  BT(5) = 1 * 14 + 1 * 5 + 2 * 2 + 5 * 1 + 14 * 1 = 42

Por lo tanto, el árbol binario total para la secuencia de pedido anticipado de longitud 5 es 42.
Usamos programación dinámica para calcular el número posible de árboles binarios. Tomamos un Node a la vez y calculamos los árboles posibles usando árboles calculados previamente. 
 

// C++ Program to count possible binary trees
// using dynamic programming
#include <bits/stdc++.h>
using namespace std;
 
int countTrees(int n)
{
    // Array to store number of Binary tree
    // for every count of nodes
    int BT[n + 1];
    memset(BT, 0, sizeof(BT));
 
    BT[0] = BT[1] = 1;
 
    // Start finding from 2 nodes, since
    // already know for 1 node.
    for (int i = 2; i <= n; ++i)
        for (int j = 0; j < i; j++)
            BT[i] += BT[j] * BT[i - j - 1];
 
    return BT[n];
}
 
// Driver code
int main()
{
    int n = 5;
    cout << "Total Possible Binary Trees are : "
        << countTrees(n) << endl;
    return 0;
}

// Java Program to count
// possible binary trees
// using dynamic programming
import java.io.*;
 
class GFG
{
static int countTrees(int n)
{
    // Array to store number
    // of Binary tree for
    // every count of nodes
    int BT[] = new int[n + 1];
    for(int i = 0; i <= n; i++)
    BT[i] = 0;
    BT[0] = BT[1] = 1;
 
    // Start finding from 2
    // nodes, since already
    // know for 1 node.
    for (int i = 2; i <= n; ++i)
        for (int j = 0; j < i; j++)
            BT[i] += BT[j] *
                     BT[i - j - 1];
 
    return BT[n];
}
 
// Driver code
public static void main (String[] args)
{
int n = 5;
System.out.println("Total Possible " +
                "Binary Trees are : " +
                       countTrees(n));
}
}
 
// This code is contributed by anuj_67.

# Python3 Program to count possible binary
# trees using dynamic programming
 
def countTrees(n) :
 
    # Array to store number of Binary
    # tree for every count of nodes
    BT = [0] * (n + 1)
 
    BT[0] = BT[1] = 1
 
    # Start finding from 2 nodes, since
    # already know for 1 node.
    for i in range(2, n + 1):
        for j in range(i):
            BT[i] += BT[j] * BT[i - j - 1]
 
    return BT[n]
 
# Driver Code
if __name__ == '__main__':
 
    n = 5
    print("Total Possible Binary Trees are : ",
                                 countTrees(n))
                                  
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)

// C# Program to count
// possible binary trees
// using dynamic programming
using System;
 
class GFG
{
static int countTrees(int n)
{
    // Array to store number
    // of Binary tree for
    // every count of nodes
    int []BT = new int[n + 1];
    for(int i = 0; i <= n; i++)
        BT[i] = 0;
        BT[0] = BT[1] = 1;
 
    // Start finding from 2
    // nodes, since already
    // know for 1 node.
    for (int i = 2; i <= n; ++i)
        for (int j = 0; j < i; j++)
            BT[i] += BT[j] *
                     BT[i - j - 1];
 
    return BT[n];
}
 
// Driver code
static public void Main (String []args)
{
    int n = 5;
    Console.WriteLine("Total Possible " +
                      "Binary Trees are : " +
                             countTrees(n));
}
}
 
// This code is contributed
// by Arnab Kundu

<?php
// PHP Program to count possible binary
// trees using dynamic programming
 
function countTrees($n)
{
    // Array to store number of Binary
    // tree for every count of nodes
    $BT[$n + 1] = array();
    $BT = array_fill(0, $n + 1, NULL);
    $BT[0] = $BT[1] = 1;
 
    // Start finding from 2 nodes, since
    // already know for 1 node.
    for ($i = 2; $i <= $n; ++$i)
        for ($j = 0; $j < $i; $j++)
            $BT[$i] += $BT[$j] *
                       $BT[$i - $j - 1];
 
    return $BT[$n];
}
 
// Driver code
$n = 5;
echo "Total Possible Binary Trees are : ",
                    countTrees($n), "\n";
 
// This code is contributed by ajit.
?>

<script>
    // Javascript Program to count
    // possible binary trees
    // using dynamic programming
     
    function countTrees(n)
    {
        // Array to store number
        // of Binary tree for
        // every count of nodes
        let BT = new Array(n + 1);
        for(let i = 0; i <= n; i++)
            BT[i] = 0;
            BT[0] = BT[1] = 1;
 
        // Start finding from 2
        // nodes, since already
        // know for 1 node.
        for (let i = 2; i <= n; ++i)
            for (let j = 0; j < i; j++)
                BT[i] += BT[j] * BT[i - j - 1];
 
        return BT[n];
    }
     
    let n = 5;
    document.write("Total Possible " + "Binary Trees are : " + countTrees(n));
                              
</script>

Producción: 
 

Total Possible Binary Trees are : 42

Complejidad temporal: O(n ² )

Espacio Auxiliar : O(n)

Alternativa: 
¡ Esto también se puede hacer usando el número catalán Cn = (2n)!/(n+1)!*n!
Para n = 0, 1, 2, 3,… los valores de los números catalanes son 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,…. También lo son los números de árboles binarios de búsqueda .

Este artículo es una contribución de Shubham Rana . 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 Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.