Determinar el recuento de Nodes Hoja en un árbol N-ario

Dado el valor de ‘N’ e ‘I’ . Aquí,  representa el número de Nodes internos presentes en un árbol N-ario y cada Node del N-ario puede tener  hijos o cero hijos. La tarea es determinar el número de Nodes Hoja en el árbol n-ario.

Ejemplos :  

Entrada: N = 3, I = 5 
Salida: Nodes hoja = 11 
 

Entrada: N = 10, I = 10 
Salida: Nodes hoja = 91 
 

Fórmula: 

donde, 
I = Número de Nodes internos. 
L = Nodes Hoja. 
y, N = Número de hijos que puede tener cada Node. 
 

Derivación: El árbol es un árbol N-ario. Suponga que tiene T Nodes totales, que es la suma de los Nodes internos (I) y los Nodes de hoja (L). Un árbol con T Nodes totales tendrá (T – 1) aristas o ramas.
En otras palabras, dado que el árbol es un árbol N-ario, cada Node interno tendrá N ramas que contribuirán a un total de N*I ramas internas. Por lo tanto tenemos las siguientes relaciones de las explicaciones anteriores,

• norte * yo = t – 1
• L + yo = T

De las dos ecuaciones anteriores, podemos decir que L = (N – 1) * I + 1.

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

// CPP program to find number
// of leaf nodes
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate
// leaf nodes in n-ary tree
int calcNodes(int N, int I)
{
    int result = 0;
 
    result = I * (N - 1) + 1;
 
    return result;
}
 
// Driver code
int main()
{
    int N = 5, I = 2;
 
    cout << "Leaf nodes = " << calcNodes(N, I);
 
    return 0;
}

// Java program to find number
// of leaf nodes
 
class GfG
{
 
// Function to calculate
// leaf nodes in n-ary tree
static int calcNodes(int N, int I)
{
    int result = 0;
 
    result = I * (N - 1) + 1;
 
    return result;
}
 
// Driver code
public static void main(String[] args)
{
    int N = 5, I = 2;
 
    System.out.println("Leaf nodes = " +
                        calcNodes(N, I));
}
}
 
// This code is contributed by Prerna Saini

# Python3 program to find number
# of leaf nodes
 
# Function to calculate
# leaf nodes in n-ary tree
def calcNodes(N, I):
    result = 0
 
    result = I * (N - 1) + 1
 
    return result
 
# Driver Code
if __name__ == '__main__':
    N = 5
    I = 2
 
    print("Leaf nodes = ",
           calcNodes(N, I))
 
# This code is contributed
# by SHUBHAMSINGH10

// C# program to find number
// of leaf nodes
using System;
 
class GFG
{
 
// Function to calculate
// leaf nodes in n-ary tree
static int calcNodes(int N, int I)
{
    int result = 0;
 
    result = I * (N - 1) + 1;
 
    return result;
}
 
// Driver code
public static void Main()
{
    int N = 5, I = 2;
 
    Console.Write("Leaf nodes = " +
                  calcNodes(N, I));
}
}
 
// This code is contributed
// by Akanksha Rai

<?php
// PHP program to find number
// of leaf nodes
 
// Function to calculate
// leaf nodes in n-ary tree
function calcNodes($N, $I)
{
    $result = 0;
 
    $result = $I * ($N - 1) + 1;
 
    return $result;
}
 
// Driver code
$N = 5; $I = 2;
 
echo "Leaf nodes = " .
      calcNodes($N, $I);
 
// This code is contributed
// by Akanksha Rai
?>

<script>
 
// Javascript program to find number
// of leaf nodes
 
// Function to calculate
// leaf nodes in n-ary tree
function calcNodes(N, I)
{
    var result = 0;
 
    result = I * (N - 1) + 1;
 
    return result;
}
 
// Driver code
var N = 5, I = 2;
 
document.write("Leaf nodes = " + calcNodes(N, I));
 
// This code is contributed by rutvik_56
 
</script>

Leaf nodes = 9

Complejidad de tiempo: O(1)

Espacio Auxiliar: O(1)