Tiempo total para visitar todos los Nodes de un árbol binario

Dado un árbol binario , encuentre el tiempo total para visitar todos los Nodes desde el Node raíz . Visitar un Node secundario desde su Node principal costará 1 unidad de tiempo y visitar el Node principal desde el Node secundario generará 0 unidades de tiempo.

Ejemplos:

Aporte: 

Salida: 5
Explicación: Los recorridos que toman 1 unidad de tiempo son 1->2, 2->4, 4->5, 1->3 y 3->6.

Aporte: 

Salida: 1

Enfoque: el problema aquí es que el tiempo total necesario será el número de aristas en el árbol binario. Entonces, la respuesta a este problema se puede encontrar para estos dos casos:

Tiempo total para visitar todos los Nodes de un árbol binario si se conoce el número de Nodes (N) : si el número de Nodes en el árbol binario ya se conoce como N , entonces el número de aristas es N-1 . Entonces, la respuesta es N-1 en este caso.

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)

Tiempo total para visitar todos los Nodes de un árbol binario si se desconoce el número de Nodes: Aplicar dfs para obtener el número de aristas y devolverlo como respuesta. Ahora siga los pasos a continuación para resolver esto:

1. Cree una función recursiva totalTime que aceptará un Node como parámetro y devolverá el número de aristas debajo de él.
2. Por lo tanto, obtenga el número de aristas en el hijo izquierdo llamando a la función totalTime para el hijo izquierdo y añadiéndole uno.
3. Repita el paso anterior para el niño correcto.
4. Al final, devuelve la suma de los bordes a la izquierda y a la derecha.
5. Imprima la respuesta de acuerdo con el enfoque anterior.

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

// C++ code for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Node of the binary tree
class Node {
public:
    int data;
    Node *left, *right;
    Node(int d)
    {
        data = d;
        left = right = NULL;
    }
};
 
// Function to find the total time taken
// to visit all nodes from the root nodes
int totalTime(Node* root)
{
 
    int l = 0, r = 0;
    if (root->left) {
        l = totalTime(root->left) + 1;
    }
    if (root->right) {
        r = totalTime(root->right) + 1;
    }
 
    return l + r;
}
 
// Driver Code
int main()
{
    // Given Binary Tree
    Node* root = new Node(1);
    root->left = new Node(2);
    root->left->left = new Node(4);
    root->left->left->left = new Node(5);
    root->right = new Node(3);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
 
    cout << totalTime(root);
    return 0;
}

// Java code for the above approach
import java.util.*;
 
class GFG{
 
// Node of the binary tree
static class Node {
 
    int data;
    Node left, right;
    Node(int d)
    {
        data = d;
        left = right = null;
    }
};
 
// Function to find the total time taken
// to visit all nodes from the root nodes
static int totalTime(Node root)
{
 
    int l = 0, r = 0;
    if (root.left!=null) {
        l = totalTime(root.left) + 1;
    }
    if (root.right!=null) {
        r = totalTime(root.right) + 1;
    }
 
    return l + r;
}
 
// Driver Code
public static void main(String[] args)
{
    // Given Binary Tree
    Node root = new Node(1);
    root.left = new Node(2);
    root.left.left = new Node(4);
    root.left.left.left = new Node(5);
    root.right = new Node(3);
    root.right.left = new Node(6);
    root.right.right = new Node(7);
 
    System.out.print(totalTime(root));
}
}
 
// This code is contributed by 29AjayKumar

# Python code for the above approach
# Node of the binary tree
class Node:
    def __init__(self, d):
        self.data = d
        self.left = None
        self.right = None
 
# Function to find the total time taken
# to visit all nodes from the root nodes
def totalTime(root):
    l = 0
    r = 0
    if (root.left):
        l = totalTime(root.left) + 1
    if (root.right):
        r = totalTime(root.right) + 1
 
    return l + r
 
# Driver Code
 
# Given Binary Tree
root = Node(1)
root.left = Node(2)
root.left.left = Node(4)
root.left.left.left = Node(5)
root.right = Node(3)
root.right.left = Node(6)
root.right.right = Node(7)
 
print(totalTime(root))
 
# This code is contributed by Saurabh jaiswal

// C# code for the above approach
using System;
public class GFG{
 
// Node of the binary tree
class Node {
 
    public int data;
    public Node left, right;
    public Node(int d)
    {
        data = d;
        left = right = null;
    }
};
 
// Function to find the total time taken
// to visit all nodes from the root nodes
static int totalTime(Node root)
{
 
    int l = 0, r = 0;
    if (root.left!=null) {
        l = totalTime(root.left) + 1;
    }
    if (root.right!=null) {
        r = totalTime(root.right) + 1;
    }
 
    return l + r;
}
 
// Driver Code
public static void Main(String[] args)
{
   
    // Given Binary Tree
    Node root = new Node(1);
    root.left = new Node(2);
    root.left.left = new Node(4);
    root.left.left.left = new Node(5);
    root.right = new Node(3);
    root.right.left = new Node(6);
    root.right.right = new Node(7);
 
    Console.Write(totalTime(root));
}
}
 
// This code is contributed by 29AjayKumar

<script>
   // JavaScript code for the above approach
 
 
   // Node of the binary tree
   class Node {
 
     constructor(d) {
       this.data = d;
       this.left = null;
       this.right = null;
     }
   };
 
   // Function to find the total time taken
   // to visit all nodes from the root nodes
   function totalTime(root) {
 
     let l = 0, r = 0;
     if (root.left) {
       l = totalTime(root.left) + 1;
     }
     if (root.right) {
       r = totalTime(root.right) + 1;
     }
 
     return l + r;
   }
 
   // Driver Code
 
   // Given Binary Tree
   let root = new Node(1);
   root.left = new Node(2);
   root.left.left = new Node(4);
   root.left.left.left = new Node(5);
   root.right = new Node(3);
   root.right.left = new Node(6);
   root.right.right = new Node(7);
 
   document.write(totalTime(root));
 
 // This code is contributed by Potta Lokesh
 </script>

6

Complejidad Temporal: O(V) donde V es el número de Nodes del árbol binario.
Espacio Auxiliar: O(1)